\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\N} {\mathset {N}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator {\emst}{emst}
\DeclareMathOperator {\conv}{CH}
\DeclareMathOperator {\argmin}{argmin}
\DeclareMathOperator {\DT}{DT}
\DeclareMathOperator {\UC}{UC}
\DeclareMathOperator {\LC}{LC}

\newtheorem {theorem} {Satz}
\newtheorem {problem}[theorem] {Problem}
\newtheorem {lemma}[theorem] {Lemma}
\newtheorem {observation}[theorem] {Observation}
\newtheorem {corollary}[theorem] {Corollary}
\newtheorem {claim}[theorem] {Claim}


\title{Versteckte Markov-Modelle}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Modell}
Ein \emph{verstecktes Markov-Modell} (Hidden Markov Model, HMM)
hat folgende Bestandteile:

\begin{enumerate}
  \item Eine endliche Zustandsmenge $Q$,
  \item ein endliches Ausgabealphabet $\Sigma$, 
  \item eine Anfangsverteilung $a_q$ f\"ur $q \in Q$ mit
    $a_q \in [0,1]$ und $\sum_{q \in Q} a_q = 1$,
  \item \"Ubergangsverteilungen $t_{qr}$ f\"ur $q,r \in Q$ mit
    $t_{qr} \in [0,1]$ und $\sum_{r \in Q} t_{qr} = 1$ f\"ur 
    jeden Zustand $q \in Q$, und
  \item Ausgabeverteilungen $o_{q\sigma}$ f\"ur $q \in Q$ 
     und $\sigma \in \Sigma$ 
      mit $o_{q\sigma} \in [0,1]$ und 
      $\sum_{\sigma \in \Sigma} o_{q\sigma} = 1$ f\"ur 
      jeden Zustand $q \in Q$.
\end{enumerate}

Ein verstecktes Markov-Modell modelliert den folgenden Zufallsprozess.

\begin{enumerate}
\item W\"ahle einen zuf\"alligen Zustand $q_0$ gem\"a\ss{} der 
Anfangsverteilung $a_q$.
\item Sei $q_i$ der aktuelle Zustand. W\"ahle eine zuf\"allige Ausgabe
   $\sigma_i$ gem\"a\ss{} der Ausgabeverteilung $o_{q_i\sigma}$.
\item W\"ahle einen zuf\"alligen Nachfolgezustand $r$ gem\"a\ss{} der 
   \"Ubergangsverteilung $t_{q_ir}$. Setze $q_{i+1} = r$ und 
   wiederhole.
\end{enumerate}

\section{Der Viterbi-Algorithmus}
Nun stellt sich folgendes Problem. Angenommen, wir beobachten eine
zuf\"allige Ausgabe $\sigma_0, \sigma_1, \dots, \sigma_{\ell-1}$. Welche Zustandsfolge hat
diese Ausgabe erzeugt?

Nat\"urlich ist diese Frage so nicht zu beantworten, da potentiell 
viele verschiedene Zustandsfolgen dieselbe Ausgabe produzieren 
k\"onnen. Dennoch k\"onnen wir eine sinnvolle Frage stellen.
Die Ausgabe $\sigma_0, \sigma_1, \dots, \sigma_{\ell-1}$ 
induziert eine Wahrscheinlichkeitsverteilung
auf den Zustandsfolgen der L\"ange $\ell$,  indem wir einer Folge
$q_0, q_1, \dots, q_{\ell-1}$ die bedingte Wahrscheinlichkeit
\[
\Pr[q_0, q_1,\dots, q_{\ell-1} \text{ Zust\"ande } \mid \sigma_0, \sigma_1,\dots, 
\sigma_{\ell-1} \text{ Ausgabe}]
\]
zuordnen. Nun suchen wir eine Zustandsfolge, die diese bedingte 
Wahrscheinlichkeit maximiert. Eine solche Zustandsfolge nennen wir
auch eine \emph{wahrscheinlichste Erkl\"arung} f\"ur die 
Ausgabe $\sigma_0, \dots, \sigma_{\ell-1}$.

Mit dem Satz von Bayes sehen wir, dass eine Zustandsfolge die bedingte
Wahrscheinlichkeit genau dann maximiert, wenn sie die Wahrscheinlichkeit

\[
\Pr[\sigma_0, \dots, \sigma_{\ell - 1} \text{ Ausgabe } \mid 
q_0, \dots, q_{\ell - 1} \text{ Zust\"ande} ] \cdot 
\Pr[q_0, \dots, q_{\ell - 1} \text{ Zust\"ande}]
\]
maximiert.
Diesen Ausdruck k\"onnen wir schreiben als
\[
o_{q_0\sigma_0} \cdot o_{q_1\sigma_1} \cdot \dots  \cdot
o_{q_{\ell-1}\sigma_{\ell-1}} \cdot a_{q_0}\cdot t_{q_0q_1} \cdot
t_{q_1q_2} \cdot \dots  \cdot t_{q_{\ell-2} q_{\ell-1}}.
\]
Nun finden wir einen effizienten Algorithmus mit Hilfe von dynamischem
Programmieren.

\begin{enumerate}
\item Finde geeignete Teilprobleme:
Definiere  $\texttt{E}[q, i]$  als die maximale Wahrscheinlichkeit 
\"uber alle Zustandsfolgen
$q_0, q_1, \dots, q_i=q$, dass das HMM die Zustandsfolge 
$q_0, q_1, \dots, q_i =q$ ausf\"uhrt und dabei die Ausgabe 
$\sigma_0, \sigma_1, \dots , \sigma_i$ produziert.

\item Finde eine Rekursion f\"ur $\texttt{E}[q, i]$:
Zu Beginn ist die Wahrscheinlichkeit, dass wir uns im Zustand $q$ befinden,
$a_q$ und die Wahrscheinlichkeit, dass $\sigma_0$ ausgegeben wird, ist 
$o_{q\sigma_0}$.
\[
  \texttt{E}[q, 0] = a_q \cdot o_{q \sigma_0}, \qquad 
  \text{ f\"ur alle } q \in Q.
\]
F\"ur die Rekursion unterscheiden wir, welches der vorletzte Zustand einer
optimalen Zustandsfolge war, und wir nehmen das Maximum.
\[
  \texttt{E}[q,i] = \max_{r \in Q} \{\texttt{E}[r, i - 1] \cdot t_{rq} 
  \cdot 
   o_{q\sigma_i}\}, \qquad \text{f\"ur $q \in Q$  und 
   $i = 1, \dots, \ell - 1$}.
\]
\item Implementiere die Rekursion: \"Ubung.
\item Finde eine optimale Zustandsfolge: \"Ubung.
\end{enumerate}

Man erh\"alt eine Laufzeit von $O(\ell|Q|^2)$ und Platzbedarf $O(\ell|Q|)$.


\end{document}