--- a/bayesian_networks/term_paper.tex	Sun Feb 10 16:53:23 2013 +0100
+++ b/bayesian_networks/term_paper.tex	Sun Feb 10 19:02:02 2013 +0100
@@ -62,6 +62,7 @@
 
 \begin{abstract}
 Bayesnetze repräsentieren mehrdimensionale Zufallsvariablen platzsparend aber exakt. Diese Arbeit führt die notwendigen Begriffe der Wahrscheinlichkeitstheorie ein und definiert den Begriff der bedingten Unabhängigkeit, anhand derer mithilfe der d-Separation die Semantik der Bayesnetze erarbeitet und deren Konstruktion erläutert wird. Schließlich wird ein Algorithmus zur exakten Inferenz vorgestellt, die im allgemeinen Fall NP-vollständig ist, auf Polytrees jedoch in Linearzeit ausgeführt werden kann.
+\todo{Konstruktion}
 \end{abstract}
 
 \vspace{3em}
@@ -386,7 +387,7 @@
     Speziell ist jeder Knoten bedingt unabhängig von
     \begin{enumerate}
         \item \emph{allen nicht-Nachfahren} gegeben seine Eltern.
-        \item \emph{allen Knoten} gegeben seine Eltern, Kinder und Eltern der Kinder.
+        \item \emph{allen anderen Knoten} gegeben seine Eltern, Kinder und Eltern der Kinder.
     \end{enumerate}
     \label{thm:bayes-independence}
 \end{theorem}
@@ -434,11 +435,11 @@
         \end{tikzpicture}
         \label{fig:bayes-independence-b}
     }
-    \caption{Bedingte Unabhängigkeit in Bayesnetzen. \protect\subref{fig:bayes-independence-a} Ein Knoten $X$ ist bedingt unabhängig von alle nicht-Nachfahren gegeben seine Eltern (rot markiert). \protect\subref{fig:bayes-independence-b} Ein Knoten $X$ ist bedingt unabhängig von allen Knoten gegeben seine Markov-Einbettung.}
+    \caption{Bedingte Unabhängigkeit in Bayesnetzen. \protect\subref{fig:bayes-independence-a} Ein Knoten $X$ ist bedingt unabhängig von alle nicht-Nachfahren gegeben seine Eltern (rot markiert). \protect\subref{fig:bayes-independence-b} Ein Knoten $X$ ist bedingt unabhängig von allen anderen Knoten gegeben seine Markov-Einbettung.}
     \label{fig:bayes-independence}
 \end{figure}
 
-Während die zweite Regel zur Konstruktion von Inferenzalgorithmen zur Anwendung kommt, kann die erste Regel direkt verwendet werden, um Einträge in der gemeinsamen Verteilung zu errechnen. Anhand des Beispieles zur erweiterten Nachmittagsplanung soll errechnet werden, wie groß die Wahrscheinlichkeit ist, dass der Student bei schönem Wetter ein schlechtes Gewissen bekommt, obwohl er Sport gemacht hat und einkaufen war, jedoch nicht gelernt hat. Einsetzen in den Produktsatz ergibt
+Während die zweite Regel bei der Konstruktion von Inferenzalgorithmen zur Anwendung kommt, kann die erste Regel direkt verwendet werden, um Einträge in der gemeinsamen Verteilung zu errechnen. Anhand des Beispieles zur erweiterten Nachmittagsplanung soll errechnet werden, wie groß die Wahrscheinlichkeit ist, dass der Student bei schönem Wetter ein schlechtes Gewissen bekommt, obwohl er Sport gemacht hat und einkaufen war, jedoch nicht gelernt hat. Einsetzen in den Produktsatz ergibt
 \begin{align*}
     \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]
@@ -466,41 +467,109 @@
 \todo[inline]{Blubberbla zu Repräsentation an dn Knoten}
 
 \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.
+
+\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.
+    $$\Pr[X \mid e] = \Pr[X = x \mid E_1 = e_1, \ldots, E_n = e_n] = \;?$$
+\end{definition}
+
+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.
+\end{example}
+
 \begin{figure}[h]
     \centering
     \begin{tikzpicture}
-        \node [net node] (schlange) {Schlange};
-        \node [net node] (mensa) at ($(schlange.center) + (-4em,\netvspace)$) {Mensa};
-        \node [net node] (schlafen) at ($(schlange.center) + (4em,\netvspace)$) {Schlafen};
-        \node [net node] (hotdog) at ($(schlange.center) - (0,\netvspace)$) {Hotdog};
+        \node [net node] (sport) {Sport};
+        \node [net node] (lernen) [right of = sport] {Lernen};
 
-        \foreach \src/\dest in {mensa/schlange, schlafen/schlange,
-        schlange/hotdog}
+        \node [net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen};
+        \node [net node] (film) at ($(sport.center) - (0,2*\netvspace)$) {Film};
+        \node [net node] (advent) at ($(lernen.center) - (0,2*\netvspace)$) {Apfelringe};
+
+        \foreach \src/\dest in {sport/gewissen, lernen/gewissen,
+        gewissen/film, gewissen/advent}
         \path [edge] (\src) -- (\dest);
 
-        \node [net cpt] at ($(schlafen.center)-(-3em,2.2em)$)
-        {$V \sim GV(0,100)$};
+
+        \node [net cpt] at ($(lernen.center)+(6em,0)$)
+        {\begin{tabu}{c}
+            $\Pr[L]$ \\     \tabucline{-}
+            $0.2$ \\
+        \end{tabu}};
 
-        \node [net cpt] at ($(mensa.center)-(1em,3em)$)
+        \node [net cpt] at ($(film.center)-(7em,0)$)
+        {\begin{tabu}{c|c}
+            G & $\Pr[M]$ \\     \tabucline{-}
+            F & $0.4$ \\
+            T & $0.75$ \\
+        \end{tabu}};
+
+        \node [net cpt] at ($(advent.center)+(7em,0)$)
+        {\begin{tabu}{c|c}
+            G & $\Pr[A]$ \\     \tabucline{-}
+            F & $0.6$ \\
+            T & $0.9$ \\
+        \end{tabu}};
+
+        \node [net cpt] at ($(sport.center)-(6em,0)$)
         {\begin{tabu}{c}
-            $\Pr[M]$ \\     \tabucline{-}
+            $\Pr[S]$ \\     \tabucline{-}
             $0.4$ \\
         \end{tabu}};
 
-        \node [net cpt] at ($(schlange.center)-(5em,3em)$)
-        {\begin{tabu}{c|c}
-            M & $S$ \\  \tabucline{-}
-            F & $S \sim N(\mu_t(v),\sigma_t)$ \\
-            T & $S \sim N(\mu_f(v),\sigma_f)$ \\
+        \node [net cpt] at ($(gewissen.center)+(7em,0)$)
+        {\begin{tabu}{cc|c}
+            S & L & $\Pr[G]$ \\     \tabucline{-}
+            F & F & $0.8$ \\
+            F & T & $0.25$ \\
+            T & F & $0.5$ \\
+            T & T & $0.1$ \\
         \end{tabu}};
+    \end{tikzpicture}
+    \caption{Bayesnetz zur Bekämpfung des schlechten Gewissens.}
+    \label{fig:inference-net}
+\end{figure}
+
+Es soll die Wahrscheinlichkeit errechnet werden, dass der Student ohne vorher Sport gemacht zu haben einen Film ansieht und dabei Apfelringe isst, also $\Pr[\neg S \mid M, A]$. Im Gegensatz zur gemeinsamen Verteilung sind hier nicht alle Variablen bestimmt, $L$ und $G$ sind versteckte Variablen. Außerdem existieren Bedingungen, die nicht unbedingt direkt mit Satz \ref{thm:bayes-independence} eliminiert werden können. Der Satz von Bayes ermöglicht es durch mehrmalige Anwendung, die Bedingung zu entfernen:
+
+\begin{align*}
+    \Pr[\neg S \mid M, A] &= \frac{\Pr[\neg S, M \mid A]}{\Pr[M} \\
+        &= \frac{\Pr[\neg S, M, A]}{\Pr[M] \cdot \Pr[A]} \\
+        &= \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 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.
 
-        \node [net cpt] at ($(hotdog.center)-(-1em,2.2em)$)
-        {$\Pr[h \mid S = s] = \Phi(\frac{-s + \mu}{\sigma})$};
-    \end{tikzpicture}
-    \caption{Echt hübsches Netz}
-    \label{fig:bn}
-\end{figure}
-\begin{figure}[h]
+\begin{align*}
+    \Pr[\neg S \mid M, A] &= \alpha \cdot \Pr[\neg S, M, A] \\
+    &= \alpha \cdot \sum_g \Pr[\neg S, M, A, g] \\
+    &= \alpha \cdot \sum_g \sum_l \Pr[\neg S, M, A, g, l] \\
+    &\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)$.
+
+\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
+    \begin{align*}
+        \Pr[X \mid e] = \alpha \cdot \sum_y \Pr[X, e, y]
+    \end{align*}
+\end{theorem}
+
+Der Ansatz kann jedoch verbessert werden, indem die Unabhängigkeiten in Bayesnetzen verwendet werden, um die Gesamtwahrscheinlichkeit direkt aus den bedingten Verteilungen zu berechnen, ohne den Umweg über die gemeinsame Verteilung gehen zu müssen.
+
+\begin{align*}
+    \Pr[\neg S \mid M, A] &= \alpha \cdot \sum_g \sum_l \Pr[\neg S, M, A, g, l] \\
+    &= \alpha \cdot \sum_g \sum_l \Pr[\neg S] \cdot \Pr[l] \cdot \Pr[g \mid \neg S, l] \cdot \Pr[M \mid g] \cdot \Pr[A \mid g] \\
+    &= \alpha \cdot \Pr[\neg S] \cdot \sum_l \Pr[l] \cdot \sum_g \Pr[g \mid \neg S, l] \cdot \Pr[M \mid g] \cdot \Pr[A \mid g]
+\end{align*}
+
+\begin{figure}[t]
     \centering
     \begin{tikzpicture}[grow=down]
         %\tikzstyle{every node} = [font=\scriptsize]
@@ -587,30 +656,17 @@
             node[left] {$\Pr[\neg S]$}
         };
     \end{tikzpicture}
-    \caption{Berechnungsbaum}
+    \caption{Berechnungsbaum erzeugt durch die verbesserte Inferenz durch Aufzählen. Unmarkierte Knoten stellen eine Multiplikation mit dem darunterliegenden Teilbaum dar, mit $+$ markierte Knoten repräsentieren Summen.}
+    \label{fig:inference-tree}
 \end{figure}
-\todo[inline]{Inferenz durch Aufzählen}
-\todo[inline]{NP-Vollständigkeit}
-\todo[inline]{Dynamische Programmierung?}
-\todo[inline]{Schätzer??}
+
+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.
 
-\begin{algorithm}
-    \KwData{this text}
-    \KwResult{how to write algorithm with \LaTeX2e }
-    initialization\;
-    \While{not at end of this document}{%
-        read current\;
-        \eIf{understand}{%
-            go to next section\;
-            current section becomes this one\;
-        }{%
-            go back to the beginning of current section\;
-        }
-    }
-    \caption{SOM-Lernalgorithmus}
-    \label{jayjay}
-\end{algorithm}
+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.
+
+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.
 
 \newpage
 \bibliographystyle{alpha}