\documentclass[a4paper]{article}

\usepackage[ngerman]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{DejaVuSerifCondensed}
\linespread{1.1}

\usepackage{amsmath}
\usepackage[thmmarks]{ntheorem}
\usepackage[pdftex]{hyperref}
\usepackage{tikz}
\usepackage{subfig}
\usepackage{wrapfig}
\usepackage{url}
\usepackage{tabu}

\usepackage{parskip}
\usepackage{graphicx}
\usepackage{todonotes}

\usetikzlibrary{calc}
\usetikzlibrary{shapes.geometric}
\tikzstyle{edge} = [draw,very thick,->,>=latex]
\tikzstyle{selected edge} = [edge, tumred]
\tikzstyle{circular node} = [circle,thick,draw,fill=tumblue!10,minimum size=12pt,inner sep=0pt,font=\bfseries]
\tikzstyle{net node} = [ellipse, draw, thick, fill=tumblue!10, minimum width=6em, minimum height=2.5em, node distance=10em, inner sep = 0]
\tikzstyle{small net node} = [net node, minimum width=3.5em, node distance=6em]
\tikzstyle{selected} = [fill=tumred!40]
\def \netvspace {6em}
\tikzstyle{net cpt} = [draw, thick, fill = tumgreen!20, font=\scriptsize, node distance=3em, inner sep = 2pt]

\xdefinecolor{tumblue}     {RGB}{0,101,189}
\xdefinecolor{tumgreen}    {RGB}{162,173,0}
\xdefinecolor{tumred}      {RGB}{229,52,24}
\xdefinecolor{tumivory}    {RGB}{218,215,203}
\xdefinecolor{tumorange}   {RGB}{227,114,34}
\xdefinecolor{tumlightblue}{RGB}{152,198,234}

\theoremstyle{break}
\newtheorem{definition}{Definition}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{theorem}[definition]{Satz}
\newtheorem{observation}[definition]{Beobachtung}
\newtheorem{example}{Beispiel}
\newtheorem*{proof}{Beweis}

\newcommand{\N}       {\mathbb{N}}
\newcommand{\Z}       {\mathbb{Z}}
\newcommand{\R}       {\mathbb{R}}
\newcommand{\Oh}      {\mathcal{O}}

\sloppy

\begin{document}
\nocite{*}

\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 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}

\setcounter{tocdepth}{3}
\setcounter{secnumdepth}{3}
\tableofcontents

\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 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.

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

\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 $\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
    \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 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}.
    \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.

\begin{example}[Erweiterte Nachmittagsplanung]
    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]
    \centering
    \begin{tikzpicture}
        \node [net node] (sport) {Sport};
        \node [net node] (kaufen) [left of = sport] {Kaufen};
        \node [net node] (lernen) [right of = sport] {Lernen};

        \node [net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen};
        \node [net node] (regen) at ($0.5*(sport.center) + 0.5*(kaufen.center) + (0,\netvspace)$) {Regen};

        \foreach \src/\dest in {regen/kaufen, regen/sport, sport/gewissen, lernen/gewissen}
        \path [edge] (\src) -- (\dest);

        \node [net cpt] at ($(regen.center)-(5.5em,0)$)
        {\begin{tabu}{c}
            $\Pr[R]$ \\     \tabucline{-}
            $0.1$ \\
        \end{tabu}};

        \node [net cpt] at ($(lernen.center)+(0,3em)$)
        {\begin{tabu}{c}
            $\Pr[L]$ \\     \tabucline{-}
            $0.2$ \\
        \end{tabu}};

        \node [net cpt] at ($(kaufen.center)-(0,3.5em)$)
        {\begin{tabu}{c|c}
            R & $\Pr[K]$ \\     \tabucline{-}
            F & $0.5$ \\
            T & $0.25$ \\
        \end{tabu}};

        \node [net cpt] at ($(sport.center)-(2em,3.5em)$)
        {\begin{tabu}{c|c}
            R & $\Pr[S]$ \\     \tabucline{-}
            F & $0.4$ \\
            T & $0.2$ \\
        \end{tabu}};

        \node [net cpt] at ($(gewissen.center)+(7em,1.1em)$)
        {\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{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. 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.

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[$\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$, $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.
        \item \emph{allen anderen 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$};
            \node [small net node] (Yn) [right of = X] {$Y_n$};

            \node [small net node] (C1) at ($0.5*(Y1.center) + 0.5*(X.center) - (0,\netvspace)$) {$C_1$};
            \node [small net node] (Cn) at ($0.5*(Yn.center) + 0.5*(X.center) - (0,\netvspace)$) {$C_n$};

            \node [small net node, selected] (P1) at ($0.5*(Y1.center) + 0.5*(X.center) + (0,\netvspace)$) {$P_1$};
            \node [small net node, selected] (Pn) at ($0.5*(Yn.center) + 0.5*(X.center) + (0,\netvspace)$) {$P_n$};

            \node [] () at ($(X.center) - (0,\netvspace)$) {$\ldots$};
            \node [] () at ($(X.center) + (0,\netvspace)$) {$\ldots$};

            \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[] {%
        \begin{tikzpicture}
            \node [small net node] (X) {X};
            \node [small net node, selected] (Y1) [left of = X] {$Y_1$};
            \node [small net node, selected] (Yn) [right of = X] {$Y_n$};

            \node [small net node, selected] (C1) at ($0.5*(Y1.center) + 0.5*(X.center) - (0,\netvspace)$) {$C_1$};
            \node [small net node, selected] (Cn) at ($0.5*(Yn.center) + 0.5*(X.center) - (0,\netvspace)$) {$C_n$};

            \node [small net node, selected] (P1) at ($0.5*(Y1.center) + 0.5*(X.center) + (0,\netvspace)$) {$P_1$};
            \node [small net node, selected] (Pn) at ($0.5*(Yn.center) + 0.5*(X.center) + (0,\netvspace)$) {$P_n$};

            \node [] () at ($(X.center) - (0,\netvspace)$) {$\ldots$};
            \node [] () at ($(X.center) + (0,\netvspace)$) {$\ldots$};

            \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{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 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]
\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 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]\\
    &= 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 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 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 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 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.
    $$\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 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]
    \centering
    \begin{tikzpicture}
        \node [net node] (sport) {Sport};
        \node [net node] (lernen) [right of = sport] {Lernen};

        \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 ($(lernen.center)+(6em,0)$)
        {\begin{tabu}{c}
            $\Pr[L]$ \\     \tabucline{-}
            $0.2$ \\
        \end{tabu}};

        \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[S]$ \\     \tabucline{-}
            $0.4$ \\
        \end{tabu}};

        \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 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. 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] \\
    &= \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]
        \tikzstyle{op} = [circular node]
        \tikzstyle{edge from parent} = [edge]

        \tikzstyle{level 2} = [sibling distance = 16em]
        \tikzstyle{level 3} = [sibling distance = 6.5em]

        \node[op] {}
        child {
            node[op] {+}
            child {
                node[op] {+}
                child {
                    node[op] {}
                    child {
                        node[op] {}
                        child {
                            node [op] {}
                            edge from parent
                            node[left] {$\Pr[A \mid g]$}
                        }
                        edge from parent
                        node[left] {$\Pr[M \mid g]$}
                    }
                    edge from parent
                    node[left] {$\Pr[g \mid \neg S, l]$}
                }
                child {
                    node[op] {}
                    child {
                        node[op] {}
                        child {
                            node [op] {}
                            edge from parent
                            node[left] {$\Pr[A \mid \neg g]$}
                        }
                        edge from parent
                        node[left] {$\Pr[M \mid \neg g]$}
                    }
                    edge from parent
                    node[right] {$\Pr[\neg g \mid \neg S, l]$}
                }
                edge from parent
                node[above left] {$\Pr[l]$}
            }
            child {
                node[op] {+}
                child {
                    node[op] {}
                    child {
                        node[op] {}
                        child {
                            node [op] {}
                            edge from parent
                            node[left] {$\Pr[A \mid g]$}
                        }
                        edge from parent
                        node[left] {$\Pr[M \mid g]$}
                    }
                    edge from parent
                    node[left] {$\Pr[g \mid \neg S, \neg l]$}
                }
                child {
                    node[op] {}
                    child {
                        node[op] {}
                        child {
                            node [op] {}
                            edge from parent
                            node[left] {$\Pr[A \mid \neg g]$}
                        }
                        edge from parent
                        node[left] {$\Pr[M \mid \neg g]$}
                    }
                    edge from parent
                    node[right] {$\Pr[\neg g \mid \neg S, \neg l]$}
                }
                edge from parent
                node[above right] {$\Pr[\neg l]$}
            }
            edge from parent
            node[left] {$\Pr[\neg S]$}
        };
    \end{tikzpicture}
    \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}

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 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.

\hfill

\bibliographystyle{alpha}
\bibliography{term_paper}

\end{document}