Mercurial > latex
changeset 60:eec0c96f4dfd
add bayesian networks, inference
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Sun, 09 Dec 2012 20:35:51 +0100 |
| parents | 564988e2790c |
| children | 0c4a2d115131 |
| files | bayesian_networks/presentation.tex |
| diffstat | 1 files changed, 281 insertions(+), 63 deletions(-) [+] |
line wrap: on
line diff
--- a/bayesian_networks/presentation.tex Sun Dec 09 00:55:42 2012 +0100 +++ b/bayesian_networks/presentation.tex Sun Dec 09 20:35:51 2012 +0100 @@ -53,9 +53,11 @@ \pgfdeclarelayer{midground} \pgfsetlayers{background,midground,main} \tikzstyle{edge} = [draw,very thick,->,>=latex] +\tikzstyle{selected edge} = [edge, tumred] \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, @@ -135,13 +137,6 @@ \end{itemize} \end{frame} -\begin{frame} - \frametitle{Aussagenlogik} - - \todo{Erschlagen durch Aussagenlogik} - \todo{Klappt nicht mit Unsicherheit} -\end{frame} - \begin{frame}[c] \frametitle{Wahrscheinlichkeitstheorie} @@ -213,6 +208,7 @@ \vspace{2em} + \begin{center} \begin{tikzpicture} \node [net node] (sport) {Sport}; \node [net cpt] [below of = sport] @@ -235,11 +231,13 @@ $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] @@ -262,6 +260,7 @@ $0.2$ \\ \end{tabu}}; \end{tikzpicture} + \end{center} \vspace{1em} \only<1>{ @@ -305,7 +304,7 @@ \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. + 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} @@ -323,7 +322,7 @@ 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. + \item \alert{Einkaufen} und \alert{Sport} beeinflussen sich nicht \end{itemize} \vfill @@ -347,11 +346,22 @@ \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,4> [selected net node] (sport) {Sport}; + \node<2> [selected net node] (kaufen) [left of = sport] {Kaufen}; + \node<3,4> [selected net node] (lernen) [right of = sport] {Lernen}; + + \node<4> [selected net node] (gewissen) at ($0.5*(sport.center) + 0.5*(lernen.center) - (0,\netvspace)$) {Gewissen}; + \node<2,3> [selected 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> { + \foreach \i/\src/\dest in {2/regen/kaufen, 2/regen/sport, + 4/sport/gewissen, 4/lernen/gewissen} + \path<\i> [selected edge] (\src) -- (\dest); + + \only<5> { \node [net cpt] at ($(regen.center)-(5em,0)$) {\begin{tabu}{c} $\Pr[R]$ \\ \tabucline{-} @@ -378,7 +388,7 @@ t & $0.2$ \\ \end{tabu}}; - \node [net cpt] at ($(gewissen.center)+(7em,0em)$) + \node [net cpt] at ($(gewissen.center)+(7em,1.1em)$) {\begin{tabu}{cc|c} S & L & $\Pr[G]$ \\ \tabucline{-} f & f & $0.8$ \\ @@ -391,42 +401,83 @@ \end{frame} \begin{frame} - \frametitle{Bayesnetze} + \frametitle{Gemeinsame Verteilung} - \begin{columns} - \begin{column}{.5\textwidth} - \todo{Eigenschaften erklären} - \end{column} - \begin{column}{.5\textwidth} - - \end{column} - \end{columns} + \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 \mathrm{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} - \frametitle{Gemeinsame Verteilung} - - \todo{Wie berechnet man den joint?} -\end{frame} - -\begin{frame} +\begin{frame}[t] \frametitle{Konstruktion} - \todo{Expertenwissen} - \todo{Reihenfolge} - \todo{Strategien: Weglassen, Struktur schaffen} + \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. + \vspace{1em} + \item Knoten modellieren \alert{quantifizierbare} Ereignisse + \begin{itemize} + \item Unbekannte Einflüsse in Verteilungen abbilden + \item Kompromiss zwischen Einfachheit und Genauigkeit + \end{itemize} + \item \alert{Lokale Struktur} schaffen + \begin{itemize} + \item Nur direkte Einflüsse abbilden + \item Kleine Einflüsse ignorieren + \end{itemize} + \item \alert{Kausale Reihenfolge} abbilden + \begin{itemize} + \item Einfacher zu fassende Verteilungen + \item Natürlichere Abbildung der Domäne + \end{itemize} + \end{itemize} \end{frame} \begin{frame} \frametitle{Knotenrepräsentation} - \todo{Diskret vs. Kontinuierlich} - \todo{Schnell vs. Genau} - \todo{Kanonische Verteilungen} + + \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 F \mid E, \neg G] = 0.6,\quad \Pr[\neg F \mid \neg E, G] = 0.2$$ + + \begin{center} + \begin{tabu}{|cc|[2pt]cc||cc|[2pt]cc|} + \hline + E & G & $\Pr[F]$ & $\Pr[\neg F]$ & E & G & $\Pr[F]$ & $\Pr[\neg F]$ \\ + \tabucline[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 11 Uhr werfe ich einen Blick auf die Länge der \alert{Schlange} und entscheide allein anhand ihrer Länge ob ich auf mein Mittagessen \alert{verzichte}.\\ + Im MI-Gebäude gibt es jeden Dienstag Hotdogs. Um genau 12 Uhr werfe ich einen Blick auf die Länge der \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} @@ -467,7 +518,7 @@ \end{tabu}}; \node [net cpt] at ($(hotdog.center)-(-1em,2.2em)$) - {$\Pr[h | S = s] = \Phi(\frac{-s + \mu}{\sigma})$}; + {$\Pr[h \mid S = s] = \Phi(\frac{-s + \mu}{\sigma})$}; \only<2> { \def\sdiv{3} @@ -479,7 +530,7 @@ \end{axis} \begin{axis}[ticks=none,very thick, - width=0.3\textwidth, yshift=-11em, xshift=-8.5em] + width=0.3\textwidth, yshift=-10em, xshift=-8.5em] \addplot[domain=0:10,smooth] {1/(1+ exp(-2*((-x+5)/1.3)))}; @@ -490,27 +541,203 @@ \begin{frame} \frametitle{Inferenz} - \todo{Problemstellung} - \todo{Approximativ, Exakt} + + \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{Aufzählen} - \todo{Summieren} - \todo{Ausklammern} + \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[F]$ \\ \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{Beispiel} - \todo{Inferenzbaum} - \todo{Mehrfache Arbeit} + \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 F, A] &= \alpha \sum_g \sum_l \Pr[\neg S, F, 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[F \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} = [circle,thick,draw,fill=tumblue!20,minimum size=12pt,inner sep=0pt, font=\bfseries] + \tikzstyle{edge from parent} = [edge] + + \tikzstyle{level 2} = [sibling distance = 15em] + \tikzstyle{level 3} = [sibling distance = 8em] + + + \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[F \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[F \mid \neg g]$} + } + edge from parent + node[right] {$\Pr[\neg g \mid \neg S, l]$} + } + edge from parent + node[above] {$\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[F \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[F \mid \neg g]$} + } + edge from parent + node[right] {$\Pr[\neg g \mid \neg S, \neg l]$} + } + edge from parent + node[above] {$\Pr[\neg l]$} + } + edge from parent + node[left] {$\Pr[\neg S]$} + }; + \end{tikzpicture} \end{frame} \begin{frame} - \frametitle{Variablenelimination} - \todo{Betrachten der Formel, Wegwerfen} - \todo{AlgorithmusIdee} - \todo{Komplexität} + \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} @@ -529,20 +756,11 @@ Bayesnetze \ldots \begin{itemize} - \item repräsentieren mehrdimensionale Zufallsvariablen - \item modellieren Kausalitätszusammenhänge + \item repräsentieren \alert{mehrdimensionale Zufallsvariablen} \item haben eine kompakte Darstellung - \item benötigen Expertenwissen - \item sparen Speicher - \item erlauben nichttriviale Interferenz + \item benötigen \alert{Expertenwissen} + \item modellieren \alert{Kausalitätszusammenhänge} + \item sparen Speicher + \item erlauben Interferenz \end{itemize} -\end{frame} - -\begin{frame} - \frametitle{Q \& A} - - \begin{center} \LARGE Danke für die Aufmerksamkeit!\end{center} - \vspace{1em} - \begin{center} \LARGE Fragen?\end{center} -\end{frame} -\end{document} +\end{frame} \end{document}