\documentclass[compress, german]{beamer}
%,hyperref={pdfpagelabels=false}

\usepackage[ngerman,english]{babel}
\uselanguage{German}
\languagepath{German}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}

\usepackage{helvet}
\usepackage{url}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{xspace} % Abstand hinter Variablennamen
\usepackage{fix-cm}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{tabu}

%\usepackage[square, sort, numbers, authoryear]{natbib}
\usepackage{todonotes}
\presetkeys{todonotes}{inline}{}

\usepackage{beamerthemeLEA2}

%\bibliographystyle{plainnat}

\newcommand{\N}       {\mathbb{N}}          % natürliche Zahlen
\newcommand{\Z}       {\mathbb{Z}}          % ganze Zahlen
\newcommand{\R}       {\mathbb{R}}          % reelle Zahlen
\newcommand{\Prob}    {\mathrm{P}}          % Wahrscheinlichkeit
\newcommand{\inter}   {\cap}                % Schnittmenge
\newcommand{\union}   {\cup}                % Vereinigung
\newcommand{\Oh}      {\mathcal{O}}         % O-Notation (Landau-Symbole)
\newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}}

\newenvironment{changemargin}[2]{%
    \begin{list}{}{%
            \setlength{\topsep}{0pt}%
            \setlength{\leftmargin}{#1}%
            \setlength{\rightmargin}{#2}%
            \setlength{\listparindent}{\parindent}%
        \setlength{\itemindent}{\parindent}%
            \setlength{\parsep}{\parskip}%
        }%
\item[]}{\end{list}}


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

\title{Bayesnetze}
\subtitle{Seminar ``Kognitive Robotik''}
\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
%\date{\today}
\date{12-12-12}
\institute{Technische Universität München}
%Inhaltsverzeichnis zu Begin von jedem Abschnitt einblenden?
%\AtBeginSection[]{
%  \begin{frame}
%    \frametitle{Outline}
%    \tableofcontents[currentsection]
%  \end{frame}
%}
%\AtBeginSection[]{
%   \begin{frame}[plain]
%       \begin{center} \LARGE\insertsectionhead \end{center}
%   \end{frame}
%}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

% Inhaltsverzeichnis
%\begin{frame}
%  \frametitle{Inhalt}
%  \tableofcontents
%\end{frame}

\begin{frame}[t]
    \frametitle{Motivation}
    Wissen ist selten \alert{sicher} oder vollständig.

    \vspace{1em}

    \begin{example} [Medizinische Diagnose]
        Software soll mögliche Ursachen für Beschwerden finden.
        \begin{center}
            \begin{columns}[c]
                \begin{column}{.35\textwidth}
                    \begin{itemize}
                        \item Vorgeschichte
                        \item Symptome
                        \item Testergebnisse
                    \end{itemize}
                \end{column}
                \begin{column}{.10\textwidth}
                    \begin{tikzpicture}[auto]
                        \useasboundingbox (0, 0.5) rectangle (1, -0.5);
                        \draw[->, >=latex, line width=.35em, black!75] (0,0) -- (1,0);
                    \end{tikzpicture}
                \end{column}
                \begin{column}{.35\textwidth}
                    \begin{itemize}
                        \item Diagnose
                        \item Therapie
                    \end{itemize}
                \end{column}
            \end{columns}
        \end{center}
    \end{example}

    Mögliche Unsicherheiten
    \begin{itemize}
        \item Vorgeschichte \alert{unvollständig}, Symptome \alert{vage}
        \item Symptome und Tests lassen mehrere \alert{Alternativen} zu
        \item Das Wissen ist \alert{fehlerbehaftet}
    \end{itemize}
\end{frame}

\begin{frame}[c]
    \frametitle{Wahrscheinlichkeitstheorie}

    \begin{definition}[Wahrscheinlichkeitsraum]
        Ein \alert{Wahrscheinlichkeitsraum} $P$ besteht aus einer Menge von \alert{Elementarereignissen} $\Omega$, \alert{Ereignissen} $A$ und einem \alert{Wahrscheinlichkeitsmaß} $\Pr$.

        \begin{itemize}
            \item $A$ ist $\sigma$-Algebra über $\Omega$
            \item $\Pr : A \mapsto [0,1]$
            \item $P = (\Omega, A, \Pr)$

                \vspace{1em}

            \item $\Pr[\Omega] = 1$
            \item $A \cap B = \emptyset \Rightarrow \Pr[A \cup B] = \Pr[A] + \Pr[B]$
        \end{itemize}
    \end{definition}
\end{frame}

\begin{frame}
    \frametitle{Wahrscheinlichkeitstheorie}

    \begin{definition}[Bedingte Wahrscheinlichkeit]
        A und B seien Ereignisse mit $\Pr[B] > 0$. Die \alert{bedingte Wahrscheinlichkeit} von A unter der Bedingung B ist dann
        $$\Pr[A\mid B] = \frac{\Pr[A \cap B]}{\Pr[B]}$$
    \end{definition}

    \begin{definition}[Unabhängigkeit]
        Zwei Ereignisse A und B sind \alert{unabhängig} wenn gilt
        $$\Pr[A \cap B] = \Pr[A] \cdot \Pr[B] = \Pr[A \mid B] \cdot \Pr[B]$$
    \end{definition}
\end{frame}

\begin{frame}[c]
    \frametitle{Wahrscheinlichkeitstheorie}

    \begin{theorem}[Produktsatz]
        Für unabhängige Ereignisse $A_i$ gilt

        $$\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{theorem}
    Also zum Beispiel
    $$\Pr[A,B,C] = \Pr[A \mid B, C] \cdot \Pr[B \mid C] \cdot \Pr[B]$$
    und
    $$\Pr[A \mid B] = \frac{\Pr[A, B]}{\Pr[B]} = \alert{\alpha} \cdot \Pr[A,B]$$
\end{frame}

\begin{frame}[c]
    \frametitle{Wahrscheinlichkeitstheorie}

    \begin{theorem}[Satz über die totale Wahrscheinlichkeit]
        Sind die Ereignisse $A_i$ paarweise disjunkt und möglich, dann gilt für ein Ereignis $B$ mit $\Pr[B] > 0$
        $$\Pr[B] = \sum_{i=1}^n \Pr[B \mid A_i] \cdot \Pr[A_i]$$
    \end{theorem}

    \begin{theorem} [Satz von Bayes]
        Für zwei Ereignisse $A$ und $B$ mit $\Pr[B] > 0$ ist
        $$\Pr[A \mid B] = \frac{\Pr[B \mid A] \cdot \Pr[A]}{\Pr[B]}$$
    \end{theorem}
\end{frame}

\begin{frame}
    \frametitle{Nachmittagsplanung}

    \begin{example}[Nachmittagsplanung]
        Ich habe einen Nachmittag lang Zeit. Ich könnte \alert{Lebensmittel kaufen}, \alert{Sport machen} oder \alert{Lernen}. Ich habe genug Zeit für alle drei. Da ich ein sehr unentschlossener Mensch bin \alert{würfle} ich mittags mit einem \alert{W20}.
    \end{example}

    \vspace{2em}

    \begin{center}
        \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}
    \end{center}
\end{frame}

\begin{frame}[t]
    \frametitle{Nachmittagsplanung}

    \begin{center}
        \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}
    \end{center}

    \vspace{1em}
    \only<1>{
        Wie groß ist die Wahrscheinlichkeit,
        \vspace{1em}
        \begin{itemize}
            \item dass ich \alert{lerne}, \alert{einkaufen} gehe, aber \alert{keinen Sport} mache?
                $$\Pr[K, \neg S, L] = \Pr[K] \cdot \Pr[\neg S] \cdot \Pr[L] = 0.5 \cdot 0.6 \cdot 0.2 = 0.06$$

            \item dass ich \alert{nicht lerne}, aber \alert{Sport mache}?
                $$\Pr[S, \neg L] = \sum_k \Pr[k] \cdot \Pr[S] \cdot \Pr[\neg L] = \Pr[S] \cdot \Pr[\neg L] = 0.32$$
        \end{itemize}
    }

    \only<2>{
        \begin{itemize}
            \item Alle möglichen Belegungen lassen sich in einer gemeinsamen Verteilung (\alert{joint distribution}) darstellen.
            \item Für \alert{$n$} binäre Zufallsgrößen hat diese aber \alert{$2^n$} Einträge.
        \end{itemize}

        \begin{center}
            \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}
        \end{center}
    }
\end{frame}

\begin{frame}
    \frametitle{Abhängigkeiten}

    \begin{example}[Erweiterte Nachmittagsplanung]
        Ich möchte das Haus nicht verlassen müssen, wenn es regnet. Deshalb halbiere ich bei \alert{Regen} die Wahrscheinlichkeit für Aktivitäten außer Haus.\\
        Wenn ich weder Sport mache noch lerne bekomme ich ein \alert{schlechtes Gewissen}. Nach meinem Würfelergebnis möchte ich wissen, wie groß die Wahrscheinlichkeit ist, am Abend schlecht gelaunt zu sein.
    \end{example}

    \vspace{1em}
    Probleme:

    \begin{itemize}
        \item $\Pr[R, S] \neq \Pr[R] \cdot \Pr[S]$
        \item Alle Sätze brauchen \alert{Unabhängigkeit}
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Bayesnetze}

    Es sind immernoch Unabhängigkeiten vorhanden:
    \begin{itemize}
        \item \alert{Regen} beeinflusst das \alert{Lernen} nicht
        \item \alert{Einkaufen} und \alert{Sport} beeinflussen sich nicht
    \end{itemize}

    \vfill

    \begin{definition}[Bedingte Unabhängigkeit]
        Zwei Ereignisse A und B sind \alert{bedingt unabhängig} unter einem Ereignis C wenn gilt

        $$\Pr[A, B \mid C] = \Pr[A \mid C] \cdot \Pr[B \mid C]$$
    \end{definition}
    Einkaufen und Sport sind \alert{bedingt unabhängig} unter Regen.
\end{frame}

\begin{frame}
    \frametitle{Bayesnetze}

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

        \node<2,3> [selected net node] (sport) {Sport};
        \node<2> [selected net node] (kaufen) [left of = sport] {Kaufen};
        \node<3> [selected net node] (lernen) [right of = sport] {Lernen};

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

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

        \foreach \i/\src/\dest in {2/regen/kaufen, 2/regen/sport, 3/sport/gewissen, 3/lernen/gewissen}
        \path<\i> [selected edge] (\src) -- (\dest);

    \end{tikzpicture}
\end{frame}

\begin{frame}[t]
    \frametitle{d-Separation}

    \begin{definition}[d-Separation]
        Zwei Knotenmengen $X$ und $Y$ sind in einem DAG $G$ durch $Z$ \alert{d-separiert} $\langle X \mid Z \mid Y \rangle_G$ wenn es \alert{keinen} (ungerichteten) Pfad zwischen $X$ und $Y$ gibt für den gilt
        \begin{enumerate}
            \item Jeder Knoten an dem Kanten \alert{zusammenlaufen} ist selbst in $Z$ oder hat einen Nachfahren in $Z$
            \item Jeder \alert{andere Knoten} ist nicht in $Z$
        \end{enumerate}
    \end{definition}

    \vfill

    \uncover<2-5> {
        \begin{center}
            \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 ($(-3*\xdist, -\ydist)$) rectangle ($(\xdist, \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 \i/\Node in {3/A, 3/B, 4/A, 4/B, 5/A, 5/E}
                \node<\i> [good dag node] at ($(\Node.center)$) {\Node};

                \foreach \i/\Node in {4/C, 5/C}
                \node<\i> [bad dag node] at ($(\Node.center)$) {\Node};

                \foreach \i/\src/\dest in {4/A/C, 4/B/C}
                \path<\i> [selected edge] (\src) -- (\dest);

                \foreach \i/\Cap in {3/$\langle A \mid \emptyset \mid B \rangle$, 4/$\neg \langle A \mid F \mid B \rangle$, 5/$\langle A \mid C \mid E \rangle$}
                \node<\i> at ($(C.center) + (-3*\xdist, 0)$) {\Cap};

            \end{tikzpicture}
        \end{center}
    }
\end{frame}

\begin{frame}
    \frametitle{Bayesnetze}

    \begin{theorem}[Unabhängigkeiten in Bayes-Netzen]
        Zufallsvariablen $X$ und $Y$ sind in einem Bayes-Netz \alert{bedingt unabhängig} unter $E$ wenn $\langle X \mid E \mid Y \rangle$.\\
        Speziell ist jeder Knoten bedingt unabhängig von
        \begin{itemize}
            \item \alert{allen nicht-Nachfahren} gegeben seine Eltern
            \item \alert{allen Knoten} gegeben seine Markov-Einbettung
        \end{itemize}
    \end{theorem}

    \begin{definition}[Markov-Einbettung]
        Die \alert{Markov-Einbettung} (Markov blanket) eines Knotens ist die Menge all seiner \alert{Eltern}, \alert{Kinder} und den \alert{Eltern aller Kinder}.
    \end{definition}
\end{frame}

\begin{frame}
    \frametitle{Bayesnetze}

    \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);

        \only<2> {
            \node [net cpt] at ($(regen.center)-(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,3em)$)
            {\begin{tabu}{c|c}
                R & $\Pr[K]$ \\     \tabucline{-}
                F & $0.5$ \\
                T & $0.25$ \\
            \end{tabu}};

            \node [net cpt] at ($(sport.center)-(2em,3em)$)
            {\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}
\end{frame}

\begin{frame}
    \frametitle{Gemeinsame Verteilung}

    \begin{theorem}[Gemeinsame Verteilung]
        Für einen Eintrag $\Pr[x_1,\ldots,x_n]$ in der gemeinsamen Verteilung eines Bayesnetzes gilt
        $$\Pr[x_1,\ldots,x_n] = \prod_{i=1}^n \Pr[x_i \mid \mathsf{parents}(X_i)]$$
    \end{theorem}

    Was ist die Wahrscheinlichkeit, dass ich ein \alert{schlechtes Gewissen} bei \alert{schönem Wetter} habe, obwohl ich \alert{Sport gemacht} habe nachdem ich \alert{einkaufen} war?
    \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] \cdot \ldots\\
        &= \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*}
\end{frame}

\begin{frame}[t]
    \frametitle{Konstruktion}
    \begin{block}{}
        Wie konstruiert man zu einer Domäne ein möglichst \alert{kompaktes}, \alert{lokal strukturiertes} und \alert{natürliches} Netz?
    \end{block}

    \begin{itemize}
        \item \alert{Expertenwissen} notwendig
            \vfill
        \item Knoten modellieren \alert{quantifizierbare} Ereignisse
            \begin{itemize}
                \item Unbekanntes in Verteilungen
                \item Einfachheit vs. Genauigkeit
            \end{itemize}
            \vspace{.2em}
        \item \alert{Lokale Struktur} schaffen
            \begin{itemize}
                \item Direkte Einflüsse
                \item Kleine Einflüsse ignorieren
            \end{itemize}
            \vspace{.2em}
        \item \alert{Kausale Reihenfolge} abbilden
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Knotenrepräsentation}

    \begin{itemize}
        \item Grundsätzlich \alert{beliebige} Verteilungen möglich
        \item Abwägung zwischen \alert{effizient} und \alert{exakt}
            \vspace{1em}
        \item Logische Verknüpfungen
        \item \alert{Kanonische} Verteilungen
    \end{itemize}

    \uncover<2>{
        \begin{example}[Noisy Or]
            Ein Patient hat Fieber, wenn er eine Erkältung oder Grippe hat. Hat er aber eine Krankheit, könnte er auch kein Fieber haben.
            $$\Pr[\neg B \mid E, \neg G] = 0.6,\quad \Pr[\neg B \mid \neg E, G] = 0.2$$

            \begin{center}
                \begin{tabu}{|cc|[1.2pt]cc||cc|[1.2pt]cc|}
                    \hline
                    E & G & $\Pr[B]$ & $\Pr[\neg B]$ & E & G & $\Pr[B]$ & $\Pr[\neg B]$ \\
                    \tabucline[1.2pt]{-}
                    F & F & 0 & 1 & T & F & 0.4 & \alert{0.6} \\
                    \hline
                    F & T & 0.8 & \alert{0.2} & T & T & 0.88 & 0.12 \\
                    \hline
                \end{tabu}
            \end{center}
        \end{example}
    }
\end{frame}

\begin{frame}
    \frametitle{Hotdogs}
    \begin{example}[Hotdog zum Mittagessen]
        Im MI-Gebäude gibt es jeden Dienstag Hotdogs. Um genau 12 Uhr werfe ich einen Blick auf die \alert{Schlange} und entscheide allein anhand ihrer Länge ob ich auf mein Mittagessen \alert{verzichte}.\\
        Die Länge der Schlange ist abhängig davon, ob es in der \alert{Mensa} akzeptables Essen gibt und wieviele Studenten \alert{verschlafen} haben.
    \end{example}

    \begin{itemize}
        \item Der Anteil der schlafenden Studenten ist \alert{gleichverteilt}.
        \item Die Länge der Schlange ist \alert{normalverteilt}.
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Hotdogs}

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

        \foreach \src/\dest in {mensa/schlange, schlafen/schlange,
        schlange/hotdog}
        \path [edge] (\src) -- (\dest);

        \node [net cpt] at ($(schlafen.center)-(-3em,2.2em)$)
        {$V \sim GV(0,100)$};

        \node [net cpt] at ($(mensa.center)-(1em,3em)$)
        {\begin{tabu}{c}
            $\Pr[M]$ \\     \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)$ \\
        \end{tabu}};

        \node [net cpt] at ($(hotdog.center)-(-1em,2.2em)$)
        {$\Pr[h \mid S = s] = \Phi(\frac{-s + \mu}{\sigma})$};

        \only<2> {
            \def\sdiv{3.2}
            \begin{axis}[label style=sloped,xlabel=Schlange,ylabel=\% schlafend, xshift=.225\textwidth,yshift=-6em,width=0.55\textwidth, colormap={tum}{color(0cm)=(tumblue); color(1cm)=(yellow); color(2cm)=(tumorange); color(3cm)=(tumred)}]
                    \addplot3[surf,domain=0:40,domain y=0:100]
                    {0.6 * exp(-0.5*((x-(30-0.25*y))/\sdiv)^2 )/(2.5*\sdiv) +
                    0.4 * exp(-0.5*((x-(15-0.1*y))/\sdiv)^2 )/(2.5*\sdiv)};
                \end{axis}

                \begin{axis}[ticks=none,very thick, width=0.3\textwidth, yshift=-10em, xshift=-8.5em]
                    \addplot[domain=0:10,smooth]
                    {1/(1+ exp(-2*((-x+5)/1.3)))};
                \end{axis}
            }
    \end{tikzpicture}
\end{frame}

\begin{frame}
    \frametitle{Inferenz}

    \begin{definition}[Inferenz]
        Für ein Netz mit Knotenmenge $K = \{X\} \cup E \cup Y$ soll die \alert{Wahrscheinlichkeit} ermittelt werden, dass eine \alert{Variable} $X$ einen Wert annimmt, unter der Bedingung, dass für die \alert{Evidenzvariablen} $E$ die Werte $e$ \alert{beobachtet} werden und die \alert{versteckten Variablen} $Y$ unbekannt sind.
        $$\Pr[X \mid e] = \Pr[X = x \mid E_1 = e_1, \ldots, E_n = e_n] = \;?$$
    \end{definition}

    Wenn ich abends ein \alert{schlechtes Gewissen} habe, wie groß ist die Wahrscheinlichkeit, dass ich \alert{nicht gelernt} habe?
    $$\Pr[\neg L \mid G] \approx 0.936$$
\end{frame}

\begin{frame}
    \frametitle{Inferenz durch Aufzählen}

    \only<1>{%
        \begin{example}[Bekämpfung des schlechten Gewissens]
            Wenn ich ein \alert{schlechtes Gewissen} habe werde ich unglücklich. Unglück kann man bekämpfen, indem man sich mit einem \alert{Film} ablenkt oder passend zur Jahreszeit Schokolade aus dem \alert{Adventskalender} isst.\\
            Zur Vereinfachung soll der Einfluss des Regens nun \alert{nicht mehr} beachtet werden.
        \end{example}
    }

    \only<2>{%
        \begin{center}
            \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)$) {Advent};

                \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}
        \end{center}
    }
\end{frame}

\begin{frame}
    \frametitle{Inferenz durch Aufzählen}

    \begin{example}
        Wie groß ist die Wahrscheinlichkeit, dass ich \alert{ohne Sport} einen \alert{Film} schaue und dabei \alert{Schokolade} esse?
    \end{example}
    Aus dem Satz der totalen Wahrscheinlichkeit erhalten wir
    $$\Pr[X \mid e] = \alpha \Pr[X, e] = \alpha \sum_y \Pr[X, e, y]$$
    also
    \begin{align*}
        \Pr[\neg S \mid M, A] &= \alpha \sum_g \sum_l \Pr[\neg S, M, A, g, l]\\
        &=\alpha \cdot \Pr[\neg S] \cdot \sum_l \Pr[l]\\
        &\qquad \cdot \sum_g \Pr[g \mid \neg S, l] \cdot \Pr[M \mid g] \cdot \Pr[A \mid g]\\
        &\approx 0.585
    \end{align*}
\end{frame}

\begin{frame}[t]
    \frametitle{Berechnungsbaum}

    \begin{tikzpicture}[grow=down]
        \tikzstyle{every node} = [font=\scriptsize]
        \tikzstyle{op} = [circular node]
        \tikzstyle{edge from parent} = [edge]

        \tikzstyle{level 2} = [sibling distance = 14em]
        \tikzstyle{level 3} = [sibling distance = 7em]

        \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}
\end{frame}

\begin{frame}
    \frametitle{Alternative Algorithmen}

    \begin{itemize}
        \item Inferenz durch Aufzählen hat \alert{exponentielle} Laufzeit
        \item Mit dynamischer Programmierung \alert{linear} auf Polytrees
        \item Aber: Exakte Interferenz ist \alert{NP-vollständig}
    \end{itemize}

    \vspace{3em}
    Alternative: \alert{Approximative Algorithmen}
    \begin{itemize}
        \item Direct/Rejection Sampling
        \item Likelihood weighting
        \item Markov chain Monte Carlo (MCMC)
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Anwendungen}
    \begin{itemize}
        \item Nachmittagsplanung
            \vspace{.2em}
        \item Krankheitsdiagnose
            \vspace{.2em}
        \item Kriminalitätsbekämpfung
            \vspace{.2em}
        \item Genanalyse
            \vspace{.2em}
        \item Entscheidungsfindung
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Zusammenfassung}

    Bayesnetze \ldots
    \begin{itemize}
        \item repräsentieren \alert{mehrdimensionale Zufallsvariablen}
        \item haben eine kompakte Darstellung
        \item benötigen \alert{Expertenwissen}
        \item modellieren \alert{Kausalitätszusammenhänge}
        \item sparen Speicher
        \item erlauben Inferenz
    \end{itemize}
\end{frame}
\end{document}