--- a/bayesian_networks/term_paper.tex	Sun Feb 10 14:48:23 2013 +0100
+++ b/bayesian_networks/term_paper.tex	Sun Feb 10 16:53:23 2013 +0100
@@ -148,7 +148,7 @@
     \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}
+    \label{lem:independent-jd}
 \end{lemma}
 \begin{proof}
     Folgt direkt aus der Definition der Unabhängigkeit.
@@ -183,11 +183,11 @@
             \end{tabu}};
         \end{tikzpicture}
         \caption{Graphische Repräsentation der Nachmittagsplanung.}
-        \label{fig:independent_net}
+        \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
+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
@@ -211,7 +211,7 @@
         \hline
     \end{tabu}
     \caption{Gemeinsame Verteilung der Nachmittagsplanung.}
-    \label{fig:independent_jd}
+    \label{fig:independent-jd}
 \end{figure}
 
 \section{Bayesnetze}
@@ -284,17 +284,116 @@
         \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.}
-    \label{fig:rain_net}
+    \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.
+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.
 
 \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.
+
+Diese Beobachtung führt zur Definition der bedingten Unabhängigkeit, eine Verallgemeinerung der im vorherigen Teil eingeführten Unabhängigkeit.
+
+\begin{definition}[Bedingte Unabhängigkeit]
+    Zwei Ereignisse A und B sind \emph{bedingt unabhängig} unter einem Ereignis C wenn gilt
+
+    \begin{align*}
+        \Pr[A, B \mid C] = \Pr[A \mid C] \cdot \Pr[B \mid C]
+    \end{align*}
+\end{definition}
+
+Um eine kompakte Form zur Berechnung von Einträgen in der gemeinsamen Verteilung zu erhalten, können bedingte Unabhängigkeiten in Bayesnetzen allgemein bestimmt werden. Dieser Begriff fällt zusammen mit einer Definition aus der Graphentheorie, der sogenannten \emph{d-Separation}.
+
+\begin{definition}[d-Separation]
+    Zwei Knotenmengen $X$ und $Y$ sind in einem DAG $G$ durch $Z$ \emph{d-separiert} $\langle X \mid Z \mid Y \rangle_G$ wenn es keinen (ungerichteten) Pfad zwischen $X$ und $Y$ gibt für den gilt
+    \begin{enumerate}
+        \item Jeder Knoten an dem Kanten zusammenlaufen ist selbst in $Z$ oder hat einen Nachfahren in $Z$
+        \item Jeder andere Knoten ist nicht in $Z$
+    \end{enumerate}
+\end{definition}
+
 \begin{figure}[h]
     \centering
-    \subfloat[Eltern] {%
+    \subfloat[$\neg \langle A \mid F \mid B \rangle$] {%
+        \begin{tikzpicture}
+            \tikzstyle {dag node} = [circular node, font=\normalfont, inner sep = 2pt, node distance = 4em]
+            \tikzstyle {bad dag node} = [dag node, fill=tumred!20]
+            \tikzstyle {good dag node} = [dag node, fill=tumgreen!20]
+
+            \def \xdist {4em}
+            \def \ydist {3em}
+
+            \useasboundingbox ($(-1.5*\xdist, -1.5*\ydist)$) rectangle ($(2.5*\xdist, 1.5*\ydist)$);
+            \node [dag node] (C) at (0,0) {C};
+            \node [dag node] (A) at ($(C.center) + (-\xdist, \ydist)$) {A};
+            \node [dag node] (B) at ($(C.center) + (\xdist, \ydist)$) {B};
+            \node [dag node] (E) at ($(C.center) + (-\xdist, -\ydist)$) {E};
+            \node [dag node] (F) at ($(C.center) + (\xdist, -\ydist)$) {F};
+            \node [dag node] (D) at ($(C.center) + (2 * \xdist, 0)$) {D};
+
+            \foreach \src/\dest in {A/C, B/C, B/D, C/F, D/F, C/E}
+            \path [edge] (\src) -- (\dest);
+
+            \foreach \Node in {A, B}
+            \node [good dag node] at ($(\Node.center)$) {\Node};
+
+            \foreach \Node in {C}
+            \node [bad dag node] at ($(\Node.center)$) {\Node};
+
+            \foreach \src/\dest in {A/C, B/C}
+            \path [selected edge] (\src) -- (\dest);
+        \end{tikzpicture}
+        \label{fig:d-separation-a}
+    }
+    \subfloat[$\langle A \mid C \mid E \rangle$] {%
+        \begin{tikzpicture}
+            \tikzstyle {dag node} = [circular node, font=\normalfont, inner sep = 2pt, node distance = 4em]
+            \tikzstyle {bad dag node} = [dag node, fill=tumred!20]
+            \tikzstyle {good dag node} = [dag node, fill=tumgreen!20]
+
+            \def \xdist {4em}
+            \def \ydist {3em}
+
+            \useasboundingbox ($(-1.5*\xdist, -1.5*\ydist)$) rectangle ($(2.5*\xdist, 1.5*\ydist)$);
+            \node [dag node] (C) at (0,0) {C};
+            \node [dag node] (A) at ($(C.center) + (-\xdist, \ydist)$) {A};
+            \node [dag node] (B) at ($(C.center) + (\xdist, \ydist)$) {B};
+            \node [dag node] (E) at ($(C.center) + (-\xdist, -\ydist)$) {E};
+            \node [dag node] (F) at ($(C.center) + (\xdist, -\ydist)$) {F};
+            \node [dag node] (D) at ($(C.center) + (2 * \xdist, 0)$) {D};
+
+            \foreach \src/\dest in {A/C, B/C, B/D, C/F, D/F, C/E}
+            \path [edge] (\src) -- (\dest);
+
+            \foreach \Node in {A, E}
+            \node [good dag node] at ($(\Node.center)$) {\Node};
+
+            \foreach \Node in {C}
+            \node [bad dag node] at ($(\Node.center)$) {\Node};
+        \end{tikzpicture}
+        \label{fig:d-separation-b}
+    }
+    \caption{Zwei Beispiele zur d-Separation. \protect\subref{fig:d-separation-a} ist keine gültige d-Separation, da F Nachfahre von C ist. \protect\subref{fig:d-separation-b} ist gültig, da C in der separierenden Menge ist und F als einziger Knoten an dem Kanten zusammenlaufen nicht.}
+    \label{fig:d-separation}
+\end{figure}
+
+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$.\\
+    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.
+    \end{enumerate}
+    \label{thm:bayes-independence}
+\end{theorem}
+
+\begin{figure}[h]
+    \centering
+    \subfloat[] {%
         \begin{tikzpicture}
             \node [small net node] (X) {X};
             \node [small net node] (Y1) [left of = X] {$Y_1$};
@@ -312,9 +411,10 @@
             \foreach \src/\dest in {X/C1, X/Cn, P1/X, Pn/X, Y1/C1, Yn/Cn}
             \path [edge] (\src) -- (\dest);
         \end{tikzpicture}
+        \label{fig:bayes-independence-a}
     }
     \hspace*{\fill}
-    \subfloat[Markov-Einbettung] {%
+    \subfloat[] {%
         \begin{tikzpicture}
             \node [small net node] (X) {X};
             \node [small net node, selected] (Y1) [left of = X] {$Y_1$};
@@ -332,9 +432,40 @@
             \foreach \src/\dest in {X/C1, X/Cn, P1/X, Pn/X, Y1/C1, Yn/Cn}
             \path [edge] (\src) -- (\dest);
         \end{tikzpicture}
+        \label{fig:bayes-independence-b}
     }
-    \caption{Non-descendants}
+    \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.}
+    \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
+\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]
+\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
+
+\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]\\
+    &= 0.5 \cdot 0.8 \cdot 0.4 \cdot 0.5 \cdot 0.9 = 0.072
+\end{align*}
+
+Da die bedingte Wahrscheinlichkeitsverteilung gerade so definiert ist, Wahrscheinlichkeiten in Abhängigkeit der Elternknoten anzugeben, sind alle verbleibenden Wahrscheinlichkeiten bekannt und der Eintrag der gemeinsamen Verteilung kann errechnet werden.
+
+\begin{theorem}[Gemeinsame Verteilung]
+    Für einen Eintrag $\Pr[x_1,\ldots,x_n]$ in der gemeinsamen Verteilung eines Bayesnetzes gilt
+    \begin{align*}
+        \Pr[x_1,\ldots,x_n] = \prod_{i=1}^n \Pr[x_i \mid \mathsf{Parents}(X_i)]
+    \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.
+\end{proof}
+
+Durch die Konstruktion der gemeinsamen Verteilung wurde gezeigt, dass Bayesnetze eine mehrdimensionale komplett und exakt beschreiben, wenn alle Abhängigkeiten korrekt repräsentiert sind.
+\todo[inline]{Blubberbla zu Repräsentation an dn Knoten}
+
+\section{Exakte Inferenz in Bayesnetzen}
 \begin{figure}[h]
     \centering
     \begin{tikzpicture}
@@ -369,10 +500,6 @@
     \caption{Echt hübsches Netz}
     \label{fig:bn}
 \end{figure}
-
-\subsection{Konstruktion}
-
-\section{Exakte Inferenz in Bayesnetzen}
 \begin{figure}[h]
     \centering
     \begin{tikzpicture}[grow=down]
@@ -467,44 +594,6 @@
 \todo[inline]{Dynamische Programmierung?}
 \todo[inline]{Schätzer??}
 
-%%%%%
-
-\section{Planarität}
-Ein \emph{Graph} $G = (V, E)$ ist ein Tupel der endlichen \emph{Knotenmenge} $V$ und \emph{Kantenmenge} $E$ aus Paaren von Knoten $(u, v)$. Im Weiteren werden nur \emph{einfache} Graphen ohne Mehrfachkanten oder Schleifen, also Kanten mit selben Anfangs- und Endknoten betrachtet, da diese keinen Einfluss auf die Planarität eines Graphen haben. Außerdem bezeichnet $n = |V|$ und $m = |E|$.
-
-Eine \emph{Zeichnung} eines Graphen ordnet jedem Knoten Koordinaten auf einer Ebene und jeder Kante eine Kurve zwischen ihren Endknoten zu. Eine Zeichnung heißt \emph{planar} wenn sich keine Kanten schneiden. Zwei Zeichnungen heißen \emph{äquivalent}, wenn ihre Reihenfolge der Kanten um jeden Knoten gleich ist. Diese Äquivalenzklasse von Zeichnungen wird \emph{Einbettung} genannt und ist planar falls eine ihrer Zeichnungen planar ist.
-
-\begin{definition}
-Ein Graph heißt \emph{planar}, wenn für ihn eine planare Zeichnung existiert.
-\end{definition}
-
-Zeichnungen unterteilen die Ebene in \emph{Flächen} mit $f$ als der Anzahl der Flächen. Es existieren abgeschlossene \emph{innere} Flächen und genau eine offene \emph{äußere} Fläche. Der eulersche Polyedersatz stellt einen Zusammenhang her zwischen der Anzahl Knoten, Kanten und Flächen in einer planaren Zeichnung.
-
-\begin{theorem}[Eulerscher Polyersatz]
-Für zusammenhängende planare Graphen gilt in jeder Zeichnung $n - m + f = 2$
-\end{theorem}
-
-Daraus ergibt sich direkt ein Kriterium zur Planaritätsprüfung anhand der Kantenanzahl.
-
-\begin{lemma}
-Für jeden planaren Graphen gilt $m \leq 3n - 6$
-\end{lemma}
-\begin{proof}
-Jede Kante kann maximal zwei Flächen begrenzen. Außerdem wird eine Fläche von mindestens drei Kanten begrenzt. Daraus ergibt sich $f \leq \frac{2m}{3}$ und $m \leq 3n - 6$.
-\end{proof}
-Dieses Lemma stellt außerdem für planare Graphen einen linearen Zusammenhang zwischen Kanten und Knoten her, es gilt $m \in \Oh(n)$, während für allgemeine Graphen nur $m \in \Oh(n^2)$ gilt.
-
-\subsection{Die Sätze von Kuratowski und Wagner}
-In den 1930er Jahren haben Kuratowski\cite{Kur30} und Wagner\cite{Wag37} erste Charakterisierungen für planare Graphen gefunden. Diese Charakterisierungen basieren auf \emph{Unterteilungen} und \emph{Minoren}. Eine Unterteilung eines Graphen entsteht durch beliebig häufiges Einfügen von neuen Knoten auf vorhandenen Kanten. Ein Graph ist Minor eines anderen Graphen, wenn er sich durch Löschen von Knoten oder Kanten oder Kantenkontraktion gewinnen lässt.
-
-\begin{theorem}
-Ein Graph ist genau dann planar wenn er keinen Teilgraphen (\emph{Kuratowski}) enthält, der eine Unterteilung von $K_5$ oder $K_{3,3}$ ist und er nicht Minor (\emph{Wagner}) eines dieser Graphen ist.
-\end{theorem}
-
-$K_5$ und $K_{3,3}$ sind also die kleinstmöglichen nicht planaren Graphen. Dieses Kriterium ist einfach zu verstehen, würde aber bei direkter Anwendung zu mindestens exponentiellen Algorithmen führen und ist deswegen zum Testen auf Planarität ungeeignet.
-
-Wurst
-
 \begin{algorithm}
     \KwData{this text}
     \KwResult{how to write algorithm with \LaTeX2e }
@@ -522,13 +611,6 @@
     \label{jayjay}
 \end{algorithm}
 
-Salat
-
-\subsection{Geschichte der Planaritätsprüfung}
-Während die Formulierung des Problems einfach ist und Kuratowski und Wagner in den dreißiger Jahren eine Charakterisierung für planare Graphen finden konnten, war längere Zeit kein effizienter Algorithmus zum Testen auf Planarität bekannt. Erst 1961 fanden Auslander und Parter\cite{AP61} einen Polynomialzeitalgorithmus basierend auf der Unterteilung von Kreisen. 1974 stellten Hopcroft und Tarjan\cite{HT74} einen ersten Linearzeitalgorithmus vor, der auf dem Betrachten einzelner Pfade im Graphen aufbaut. Diese Algorithmen verwenden jedoch meist komplexe Datenstrukturen und sind relativ schwer zu implementieren.
-
-Im Folgenden soll das \emph{LR-Planaritätskriterium} vorgestellt werden, das auf der Tiefensuche basiert und ursprünglich von de Fraysseix, Ossona de Mendez und Rosenstiehl 2006\cite{FMR06} veröffentlicht und 2009 von Brandes\cite{Bra09} näher beschrieben wurde.
-
 
 \newpage
 \bibliographystyle{alpha}