Mercurial > latex
changeset 78:7832b30c28a9
add new markov-figure, tree
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Sat, 09 Feb 2013 00:56:47 +0100 |
| parents | 49fd0ad78c3a |
| children | 8e25541f4f26 |
| files | bayesian_networks/term_paper.tex |
| diffstat | 1 files changed, 171 insertions(+), 40 deletions(-) [+] |
line wrap: on
line diff
--- a/bayesian_networks/term_paper.tex Fri Feb 08 23:54:04 2013 +0100 +++ b/bayesian_networks/term_paper.tex Sat Feb 09 00:56:47 2013 +0100 @@ -25,10 +25,11 @@ \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 {7em} +\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} @@ -142,10 +143,176 @@ \section{Bayesnetze} \subsection{Semantik} +\begin{figure}[h] + \centering + \subfloat[Eltern] {% + \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} + } + \hspace*{\fill} + \subfloat[Markov-Einbettung] {% + \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} + } + \caption{Non-descendants} +\end{figure} +\begin{figure}[h] + \centering + \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})$}; + \end{tikzpicture} + \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] + %\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} +\end{figure} \todo[inline]{Inferenz durch Aufzählen} \todo[inline]{NP-Vollständigkeit} \todo[inline]{Dynamische Programmierung?} @@ -185,42 +352,6 @@ 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} -\begin{figure}[h] - \centering - \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})$}; - \end{tikzpicture} - \caption{Echt hübsches Netz} - \label{fig:bn} -\end{figure} - $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