--- a/bayesian_networks/term_paper.tex	Wed Feb 06 21:42:11 2013 +0100
+++ b/bayesian_networks/term_paper.tex	Fri Feb 08 23:54:04 2013 +0100
@@ -1,8 +1,11 @@
-\documentclass[12pt,a4paper]{article}
+\documentclass[a4paper]{article}
 
 \usepackage[ngerman]{babel}
 \usepackage[T1]{fontenc}
 \usepackage[utf8]{inputenc}
+\usepackage{DejaVuSerif}
+%\usepackage{lmodern}
+\linespread{1.1}
 
 \usepackage{amsmath}
 \usepackage[thmmarks]{ntheorem}
@@ -35,10 +38,11 @@
 \xdefinecolor{tumorange}   {RGB}{227,114,34}
 \xdefinecolor{tumlightblue}{RGB}{152,198,234}
 
+\theoremstyle{break}
 \newtheorem{definition}{Definition}
 \newtheorem{lemma}[definition]{Lemma}
-\newtheorem{theorem}[definition]{Theorem}
-\newtheorem{proof}[definition]{Beweis}
+\newtheorem{theorem}[definition]{Satz}
+\newtheorem*{proof}{Beweis}
 \newtheorem{observation}[definition]{Beobachtung}
 
 \newcommand{\N}       {\mathbb{N}}
@@ -48,43 +52,100 @@
 
 \sloppy
 
-
 \begin{document}
 \nocite{*}
 
 \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.
+\end{abstract}
+
+\vspace{3em}
+
 \setcounter{tocdepth}{3}
 \setcounter{secnumdepth}{3}
 \tableofcontents
 
-\vspace{3em}
+
+\newpage
+
+\section{Unsicheres Wissen}
+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]$.
+
+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.
 
-\begin{abstract}
-    Abstract?
-\end{abstract}
+Oft soll die Wahrscheinlichkeit für ein Ereignis $A$ bestimmt werden, wenn schon bekannt ist, dass andere Ereignisse $B$, sogenannte \emph{Evidenzen}, eingetreten sind. Diese Wahrscheinlichkeit nennt man \emph{bedingte Wahrscheinlichkeit}.
+\begin{definition}[bedingte Wahrscheinlichkeit]
+    Seien $A$ und $B$ Ereignisse mit $\Pr[B] > 0$. Dann ist
+    \begin{align*}
+        \Pr[A\mid B] = \frac{\Pr[A \cap B]}{\Pr[B]}
+    \end{align*}
+    die \emph{bedingte Wahrscheinlichkeit} von $A$ unter der Bedingung $B$.
+\end{definition}
+
+Diese Definition erlaubt die Einführung des Begriffs der stochastischen \emph{Unabhängigkeit}. Zwei Ereignisse sind dann unabhängig, wenn Wissen über das eine Ereignis die Wahrscheinlichkeit des anderen Ereignisses nicht beeinflusst.
 
 \newpage
 
-\section{Bedingte Unabhängigkeit}
-\todo[inline]{Einleitung}
-\todo[inline]{DWT}
-\todo[inline]{Bedingte Unabhängigkeit}
+\begin{definition}[Unabhängigkeit]
+    Sind $A$ und $B$ mögliche Ereignisse, dann ist $A$ von $B$ \emph{unabhängig} wenn
+    \begin{align*}
+        \Pr[A \mid B] = \Pr[A]
+    \end{align*}
+\end{definition}
+
+Unter Verwendung der bedingten Wahrscheinlichkeit lässt sich zeigen, dass diese Definition äquivalent ist zu:
+
+\begin{lemma}
+    $A$ ist unabhängig von $B$ genau dann wenn
+    \begin{align*}
+        \Pr[A \cap B] &= \Pr[A] \cdot \Pr[B] \\
+        &= \Pr[A \mid B] \cdot \Pr[B]
+    \end{align*}
+\end{lemma}
+
+Mit diesen Begriffen können drei wichtige Sätze der Wahrscheinlichkeitstheorie hergeleitet werden:
+
+\begin{theorem}[Produktsatz]
+    Für unabhängige Ereignisse $A_i$ gilt
+    \begin{align*}
+        \Pr\left[\, \bigcap_{i=1}^n A_i \right] =
+        \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.
+
+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.
+
+\begin{theorem}[Satz über die totale Wahrscheinlichkeit]
+    Bilden die Ereignisse $A_1, \ldots, A_n$ eine vollständige Ereignisdisjunktion, dann gilt für die Wahrscheinlichkeit eines Ereignisses $B$
+    \begin{align*}
+        \Pr[B] = \sum_{i=1}^n \Pr[B \mid A_i] \cdot \Pr[A_i]
+    \end{align*}
+\end{theorem}
+
+Der Satz von Bayes stellt eine Verbindung her zwischen der Bedingung eines Ereignisses $A$ unter einem anderen Ereignis $B$ und der Wahrscheinlichkeit, dass beide Ereignisse gleichzeitig eintreten. Der Satz illustriert die Interpretation, dass eine bedingte Wahrscheinlichkeit eine Renormalisierung von bereits bekannten Wahrscheinlichkeiten darstellt, indem der Ereignisraum eingeschränkt wird.
+
+\begin{theorem}[Satz von Bayes]
+    Für zwei Ereignisse $A$ und $B$ mit $\Pr[B] > 0$ gilt
+    \begin{align*}
+        \Pr[A \mid B] &= \frac{\Pr[B \mid A] \cdot \Pr[A]}{\Pr[B]} \\
+        &= \frac{\Pr[A, B]}{\Pr[B]}
+    \end{align*}
+\end{theorem}
+
+Zur Vereinfachung der Notation verwendet man oft $\Pr[A,B]$ statt $\Pr[A \cap B]$.
 
 \section{Bayesnetze}
-\todo[inline]{Motivation}
-
 \subsection{Semantik}
-\todo[inline]{Unabhängigkeiten, d-Separation}
-\todo[inline]{Joint Distribution}
-\todo[inline]{Komplexität}
 
 \subsection{Konstruktion}
-\todo[inline]{Reihenfolge der Knoten}
-\todo[inline]{Kontinuierliche Netze}
-\todo[inline]{Kanonische Verteilungen}
 
-\section{Inferenz in Bayesnetzen}
+\section{Exakte Inferenz in Bayesnetzen}
 \todo[inline]{Inferenz durch Aufzählen}
 \todo[inline]{NP-Vollständigkeit}
 \todo[inline]{Dynamische Programmierung?}