--- a/bayesian_networks/term_paper.tex	Sat Feb 09 00:56:47 2013 +0100
+++ b/bayesian_networks/term_paper.tex	Sun Feb 10 14:22:07 2013 +0100
@@ -3,7 +3,7 @@
 \usepackage[ngerman]{babel}
 \usepackage[T1]{fontenc}
 \usepackage[utf8]{inputenc}
-\usepackage{DejaVuSerif}
+\usepackage{DejaVuSerifCondensed}
 %\usepackage{lmodern}
 \linespread{1.1}
 
@@ -40,11 +40,13 @@
 \xdefinecolor{tumlightblue}{RGB}{152,198,234}
 
 \theoremstyle{break}
+\qedsymbol{\Omega}
 \newtheorem{definition}{Definition}
 \newtheorem{lemma}[definition]{Lemma}
 \newtheorem{theorem}[definition]{Satz}
+\newtheorem{observation}[definition]{Beobachtung}
+\newtheorem{example}{Beispiel}
 \newtheorem*{proof}{Beweis}
-\newtheorem{observation}[definition]{Beobachtung}
 
 \newcommand{\N}       {\mathbb{N}}
 \newcommand{\Z}       {\mathbb{Z}}
@@ -59,7 +61,7 @@
 \input{titlepage}
 
 \begin{abstract}
-    Bayesnetze stellen eine Möglichkeit dar, mehrdimensionale Zufallsvariablen platzsparend aber exakt zu repräsentieren. Diese Arbeit führt die notwendigen Begriffe der Wahrscheinlichkeitstheorie ein und Definiert den Begriff der bedingten Unabhängigkeit. Dieser stellt die Basis von Bayesnetzen dar, deren Semantik und 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.
+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.
 \end{abstract}
 
 \vspace{3em}
@@ -118,7 +120,7 @@
         \prod_{i=1}^n \Pr \left[ A_i \left| \bigcap_{k=1}^{i-1}A_k \right.\right]
     \end{align*}
 \end{theorem}
-Die Wahrscheinlichkeit, dass mehrere unabhängige Ereignisse gleichzeitig Eintreten lässt sich also darstellen, als eine mit Produkten verknüpfte Kette von bedingten Wahrscheinlichkeiten, die immer kürzer wird.
+Die Wahrscheinlichkeit, dass mehrere unabhängige Ereignisse gleichzeitig eintreten lässt sich also darstellen als eine mit Produkten verknüpfte Kette von bedingten Wahrscheinlichkeiten, die immer kürzer wird.
 
 Man nennt eine Menge von Ereignissen eine \emph{vollständige Ereignisdisjunktion} wenn kein Paar von Ereignissen gleichzeitig eintreten kann und gemeinsam alle Elementarereignisse abgedeckt werden. Für eine solche Disjunktion kann die Wahrscheinlichkeit eines Ereignisses ausgedrückt werden, indem alle Alternativen addiert werden.
 
@@ -139,9 +141,94 @@
     \end{align*}
 \end{theorem}
 
-Zur Vereinfachung der Notation verwendet man oft $\Pr[A,B]$ statt $\Pr[A \cap B]$.
+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.
+
+\begin{lemma}
+    Für unabhängige Zufallsvariablen $A_1, \ldots, A_n$ gilt
+    \begin{align*}
+        \Pr[A_1=a_1, \ldots, A_n=a_n] = \Pr[A_1=a_1] \cdot \ldots \cdot \Pr[A_n=a_n]
+    \end{align*}
+    \label{lem:independent_jd}
+\end{lemma}
+\begin{proof}
+    Folgt direkt aus der Definition der Unabhängigkeit.
+\end{proof}
+
+Für einfache Problemstellungen führt dieses Lemma direkt zu einer Kompakten darstellung der gemeinsamen Verteilung.
+
+\begin{example}[Nachmittagsplanung]
+    Ein Student kann an einem Nachmittag Lebensmittel kaufen, Sport machen oder lernen. Er hat genügend Zeit für alle drei Tätigkeiten. Am Mittag entscheidet er für jede mögliche Tätigkeit mit Hilfe eines Würfelwurfs, ob er sie ausüben möchte.
+    \begin{figure}[h]
+        \centering
+        \begin{tikzpicture}
+            \node [net node] (sport) {Sport};
+            \node [net cpt] [below of = sport]
+            {\begin{tabu}{c}
+                $\Pr[S]$ \\     \tabucline{-}
+                $0.4$ \\
+            \end{tabu}};
+
+            \node [net node] (kaufen) [left of = sport] {Kaufen};
+            \node [net cpt] [below of = kaufen]
+            {\begin{tabu}{c}
+                $\Pr[K]$ \\     \tabucline{-}
+                $0.5$ \\
+            \end{tabu}};
+
+            \node [net node] (lernen) [right of = sport] {Lernen};
+            \node [net cpt] [below of = lernen]
+            {\begin{tabu}{c}
+                $\Pr[L]$ \\     \tabucline{-}
+                $0.2$ \\
+            \end{tabu}};
+        \end{tikzpicture}
+        \caption{Graphische Repräsentation der Nachmittagsplanung.}
+        \label{fig:independent_net}
+    \end{figure}
+\end{example}
+
+Das Ergebnis jedes Würfelwurfes ist von allen vorherigen Würfen unabhängig, es kann Lemma \ref{lem:independent_jd} angewendet werden. Für die Wahrscheinlichkeit, Sport zu machen, zu lernen aber nicht einkaufen zu gehen gilt also
+\begin{align*}
+    \Pr[K, S, \neg L] &= \Pr[K] \cdot \Pr[S] \cdot \Pr[\neg L] \\
+    &= 0.5 \cdot 0.4 \cdot 0.8 = 0.16
+\end{align*}
+
+Zwar existieren exponentiell viele Kombinationen, diese müssen jedoch nicht alle explizit gespeichert werden, da sie sich aus linear vielen Informationen -- den Einzelverteilungen -- errechnen lassen.
+
+\begin{figure}[t]
+    \centering
+    \begin{tabu}{|ccc|[1.2pt]c||ccc|[1.2pt]c|}
+        \hline
+        K & S & L & $\Pr$ & K & S & L & $\Pr$ \\
+        \tabucline[1.2pt]{-}
+        F & F & F & 0.24 & T & F & F & 0.24 \\
+        \hline
+        F & F & T & 0.06 & T & F & T & 0.06 \\
+        \hline
+        F & T & F & 0.16 & T & T & F & 0.16 \\
+        \hline
+        F & T & T & 0.04 & T & T & T & 0.04 \\
+        \hline
+    \end{tabu}
+    \caption{Gemeinsame Verteilung der Nachmittagsplanung.}
+    \label{fig:independent_jd}
+\end{figure}
 
 \section{Bayesnetze}
+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.
+\begin{definition}[Bayesnetz]
+    Ein Bayesnetz ist ein gerichteter azyklischer Graph, ein \emph{DAG}.
+    \begin{enumerate}
+        \item Jeder Knoten repräsentiert eine diskrete oder kontinuierliche Zufallsvariable.
+        \item Existiert eine Kante vom Knoten $X$ zum Knoten $Y$, dann heißt $X$ \emph{Elternknoten} von $Y$. Es existieren keine Kreise.
+        \item Jeder Knoten $X_i$ besitzt eine \emph{bedingte Wahrscheinlichkeitsverteilung} $\Pr[X_i \mid \mathsf{Parents}(X_i)]$.
+    \end{enumerate}
+\end{definition}
+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.
+
 \subsection{Semantik}
 \begin{figure}[h]
     \centering