
%\subsection{Hidden Markov-Model}

\subsubsection{Vorwort} Namensgeber des Modells ist sein Entwickler
Andrei Andrejewitsch Markov (1856 - 1922), der wesentliche
Beitr\"{a}ge zur Wahrscheinlichkeitstheorie und Analysis
beisteuerte. Er berechnete 1913 die Buchstabensequenzen in
russischer Literatur um die Notwendigkeit der Unabh\"{a}ngigkeit
f\"{u}r das Gesetz der grossen Zahlen nachzuweisen. Die Berechnungen
konnten zudem als Aussage \"{u}ber die Wohlgeformtheit der
Orthographie von Buchstabenketten interpretiert werden. Aus diesem
Ansatz entwickelte sich ein allgemeines statistisches Werkzeug, der
sogenannte stochastische Markov-Prozess, basiert auf dieser Methode
findet heute sich eine Anwendung f\"{u}r unsere Projektgruppe
sogenannter Hidden Markov-Models bzw. in der NER \footnote{Named
Entity Recognition}.

\subsubsection{Markov-Prozess}
Der Markov-Prozess wird allgemein synonym zur Markov-Kette
verwendet, allgemeiner da sich die Verteilungsfunktion zu einem
beliebigen, auch nicht- diskretem Zeitpunkt bestimmen l\"{a}sst. In
der Computertechnik kommen die spezielleren Markov-Ketten zum
Einsatz.

\subsubsection{Markov-kette}
Eine Markow-Kette ist eine spezielle Klasse von stochastischen
Prozessen. Man unterscheidet eine Markow-Kette in diskreter und in
stetiger Zeit. Markow-Ketten in stetiger Zeit werden meistens als
Markow-Prozess bezeichnet. Das System springt bei jedem Zeitschritt
von einem Zustand in den n\"{a}chsten, dem zeitlichen Fortschreiten
liegt eine \"{U}bergangswahrscheinlichkeit zugrunde. Das Spezielle
einer Markow-Kette ist die Eigenschaft, dass durch Kenntnis einer
begrenzten Vorgeschichte ebensogute Prognosen \"{u}ber die
zuk\"{u}nftige Entwicklung m\"{o}glich sind wie bei Kenntnis der
gesamten Vorgeschichte des Prozesses. Im Falle einer Markow-Kette
erster Ordnung hei{\ss}t das: Die Zukunft des Systems h\"{a}ngt nur
von der Gegenwart (dem aktuellen Zustand) und nicht von der
Vergangenheit ab. Um diese Eigenschaft anschaulich zu beschreiben
sagt man auch, dass eine Markovkette "`Ged\"{a}chtnislos"' ist.
Ausserdem besagt die Ordnungszahl einer Markov-Kette, von wie viel
vorherigen Zust\"{a}nden der aktuelle Zustand abh\"{a}ngt. Bei der
Markov-Ketten $1.$ Ordnung h\"{a}ngt der aktuelle Zustand und seine
Ausgabe nur vom seinem vorherigen Zustand ab, mathematisch
ausgedruckt:

\begin{center}
  \begin{eqnarray}
       P(q_t & = & S_j|q_{t-1} =S_i, q_{t-2}=S_k, \ldots) \nonumber \\
             & = & P(q_t=S_j|q_{t-1}=S_i) \nonumber
  \end{eqnarray}
\end{center}

Um Markov-Kette zu modellieren, m\"{u}ssen sie aus die folgenden
Elemente bestehen:
\begin{itemize}
  \item die Menge der Zust\"ande $S = \{s_1,s_2,\ldots,s_N\}$
  \item $a_{ij}$ ist die Wahrscheinlichkeit, dass das System in den Zustand
  $s_j$ \"{u}bergeht unter der Vorraussetzung, dass das System sich im
  Zustand $s_i$ befindet, wobei die Summe aller \"{U}bergangswahrscheinlichkeiten
  in einem Zustand bzw. einer Zeile der Matrix zusammen $1$ ergeben m\"{u}ssen.
  \begin{center}
  \begin{equation}
  a_{ij} = P(q_{t+1}=s_j|q_t=s_i), 1{\leq}i,j{\leq}N
  \end{equation}
  \end{center}
  \begin{center}
  \begin{equation}
  a_{ij}{\geq}0, \sum_{i=1}^{N} a_{ij}=1
  \end{equation}
  \end{center}
  \item Anfangswahrscheinlichkeitenvektor $pi=\{\pi_i\}$, der den Anfangszustand
  des Systems beschreibt.
  \begin{center}
  \begin{equation}
  \pi_i = P(q_1 = s_i), 1{\leq}i{\leq}N
  \end{equation}
  \end{center}
\end{itemize}
Ein Markov-Modell ist eine Datenstruktur, die die n\"{o}tigen Werte
f\"{u}r die Steuerung einer Markov-Kette bereitstellt. hier
beschreibt das urspr\"{u}ngliche, einfache Modell zu einem Modell
zur Vorhersage auf Grundlage indirekter Evidenz (Hidden
Markov-Modell).

\begin{center}
\begin{figure}  
\includegraphics[width=0.6\textwidth]{bilder_wei/mm.png}
  \caption{Wettervorhersage mit dem Markov Modell}
\end{figure}
\end{center}
Hier benutze ich das popul\"{a}re Beispiel vom Markov-Modell,
n\"{a}mlich ist das System der Wettervorhersage, welches einfach mit
Zwei Zust\"{a}nde aufgebaut ist: Regen und Sonne.\\
\"{U}bergangswahrscheinlichkeiten:

\begin{center}
\[P(Regen|Regen)=0.3, P(Sonne|Regen)=0.7\]\\
\[P(Regen|Sonne)=0.2, P(Sonne|Sonne)=0.8\]\\
\[A = \{a_{ij}\} = \begin{pmatrix}
                        & 0.3 & 0.2\\
                        & 0.7 & 0.8\\
                 \end{pmatrix}
                 \]
\end{center}

Anfangswahrscheinlichkeiten: \[P(Regen)=0.4, P(Sonne)=0.6\]\\
Nehmen wir an, dass wir eine Beobachtungsfolge der Zust\"{a}nde in
unserem Beispiel errechnen m\"{o}chten: \{Sonne, Sonne, Regen,
Regen\}.

\begin{eqnarray}
P({Sonne, Regen}) & = & P(Sonne) P(Sonne|Sonne) P(Regen|Sonne) P(Regen|Regen) \nonumber\\
                  & = & 0.6*0.8*0.2*0.3 \nonumber \\
                  & = & 0.0288 \nonumber
\end{eqnarray}

\subsubsection {Hidden Markov-Model}
Heute finden wir HMM-Technik \"{u}berall vor, wo (Zeit)seriendaten
zu modellieren, interpretieren, segmentieren sind und wo einen
Erwerb umfangreicher Trainingsdatensammlungen mit passendem Aufwand
zu vollziehen ist. Sie machen auf die vielfalt von technischen
Anwendungen, einige bekannten Anwendungsgebieten sind:

\begin{itemize}
  \item Gen-Vorhersage
  \item Spracherkennung und Mustererkennung
  \item Signal-Verarbeitung
  \item Neurobiologie
  \item \ldots
\end{itemize}

mit Hilfe von Hidden Markov-Modellen kann man nach bestimmten
Sequenzen oder auch Mustern in Daten suchen. Bei allen diesen
Anwendungsm\"{o}glichkeiten werden bestimmte Muster in grossen
Datenmengen gesucht, die Mustersuche in Datenbanken wird als
Data-Mining bezeichnet.\\[0.3cm]
Das Hidden Markov-Modell, ist aus allgemeinem Markov-Modell ein
erweitertes stochastisches Modell, das sich durch zwei
Zufallsprozesse beschreiben l\"{a}sst. Der erste Zufallsprozess
entspricht dabei einer Markov-Kette, die durch Zust\"{a}nde und
\"{U}bergangswahrscheinlichkeiten gekennzeichnet ist. Die
Zust\"{a}nde der Kette sind von au{\ss}en jedoch nicht direkt
sichtbar (sie sind verborgen). Stattdessen erzeugt ein zweiter
Zufallsprozess zu jedem Zeitpunkt beobachtbare Ausgangssymbole
gem\"{a}{\ss} einer zustandsabh\"angigen
Wahrscheinlichkeitsverteilung. Die Aufgabe besteht h\"aufig darin,
aus der Sequenz der Ausgabesymbole auf die Sequenz der verborgenen
Zust\"{a}nde zu schlie{\ss}en. %\\[0.3cm]
\paragraph{Definition}\cite{Rabiner/89a} ein Hidden Markov-Modell
wird formal als F\"{u}nftupel $\lambda = (N,M,A,B,\pi)$ definiert:
\begin{itemize}
  \item $N$ ist die Menge aller Zust\"{a}nde $S = \{s_1,s_2,\ldots,s_N\}$
  im HMM die Zustandsvariable $Q = q_1q_2{\ldots}q_T$ annehmen kann.
  \item $M$ ist Merkmalsraum (oft als Ausgabealphabet bezeichnet),
  also der Definitionsbereich von $b_i$. Dieser kann diskret,
  oder kontinuierlich sein. Je nach dem ist $b_i$ eine
  Wahrscheinlichkeit oder eine Dichte. Wahrscheinlichkeit,
  dass $q_i$ der Startzustand ist.
  \item $A = \{a_{ij}\}$ Zustands\"{u}bergangsmatrix, wobei $a_{ij}$ die
  Wahrscheinlichkeit angibt, dass nach Zustand $q_i$
  in Zustand $q_j$ gewechselt wird.
  \item $B = \{b_1,\ldots,b_n\}$ Menge der
  Emissionswahrscheinlichkeitsverteilungen bzw. Dichten
  \item $b_i(k)$ Wahrscheinlichkeit im Zustand $q_i$
  die Beobachtung k zu machen
  \item $\pi=\{\pi_i\}$ Anfangswahrscheinlichkeitsverteilung mit
  \begin{center}
  \begin{equation}
  \pi_i = P(q_1 = s_i), 1{\leq}i{\leq}N
  \end{equation}
  \end{center}
\end{itemize}
Gegeben seien die passenden Werte von $N$, von $M$, von $A$, von $B$
und von $\pi$ das HMM kann als Generator verwendet werden, um eine
Beobachtung Reihenfolge anzugeben, in der jede Beobachtung $O_t$
eins der Symbole von V ist und T die Zahl Beobachtungen in der Folge
wie folgen ist. Das oben genannte Verfahren kann verwendet werden
als Generator von Beobachtungen und als Modell f\"{u}r, wie eine
gegebene Beobachtung Reihenfolge durch ein passendes HMM erzeugt
wurde. Genauer diese Schrittfolge\cite{Rabiner/89a} sieht man direkt
unten ein.
\begin{enumerate}
  \item w\"{a}hle Anfangszustand $q_i = s_i$ entsprechend
  Anfangszustandverteilung $\pi$
  \item Setze $t = 1$
  \item W\"{a}hle $O_t = v_k$ entsprechend Wahrscheinlichkeitsverteilung
   der Beobachtungssymbole im Zustand $s_i$, d.h. $b_i(k)$
  \item Wechsle in den n\"achsten Zustand $q_{t+1} = s_i$
  entsprechend \"{u}bergangswahrscheinlichkeitsverteilung $a_{ij}$
  f\"{u}r Zustand $s_i$
  \item setze $t = t + 1$, wiederhole Schritt $3$, falls $t < T$,
  sonst endet dies Verfahren
\end{enumerate}
In der vordere Vorstellung haben wir schon gesehen, wie das System
der Wettervorhersage mit Hilfe des allgemeinen Markov-Modells
aussieht. und jetzt kucken wir nochmal das erweiterte System,
welches aus dem Markov-Modell evolviert ist, an.

\begin{center}
\begin{figure}
  \includegraphics[width=0.6\textwidth]{bilder_wei/hmm.png}\\
  \caption{Wettervorhersage mit dem Hidden Markov-Modell}
\end{figure}
\end{center}

Zwei Zust\"{a}nde vom Luftdruck:
\begin{center}
niedrig oder hoch
\end{center}
Zwei Beobachtungen:
\begin{center}
Regen und Sonne
\end{center}
\"{U}bergangswahrscheinlichkeiten:
\begin{center}
\[P(niedrig|niedrig)=0.3,P(hoch|niedrig)=0.7\]\\
\[P(niedrig|hoch)=0.2, P(hoch|hoch)=0.8\]\\
\[A = {a_{ij}} = \begin{pmatrix}
                        & 0.3 & 0.2\\
                        & 0.7 & 0.8\\
                 \end{pmatrix}
                 \]
\end{center}
Ausgabewahrscheinlichkeiten:
\begin{center}
\[P(Regen|niedrig)=0.6,P(Sonne|niedrig)=0.4\]\\
\[P(Regen|hoch)=0.4, P(Sonne|hoch)=0.3\]
\end{center}
Anfangswahrscheinlichkeiten: \[P(niedrig)=0.4 , P(hoch)=0.6\]\\
hier als Beispiel k\"{o}nnen wir versuchen, alle m\"{o}gliche
Reihenfolge der versteckten Zust\"{a}nde anzunehmen:
\begin{eqnarray}
P({Sonne, Regen}) & = & P({Sonne, Regen},{niedrig, niedrig}) \nonumber \\
                  & + & P({Sonne, Regen}, {niedrig, hoch}) \nonumber \\
                  & + & P({Sonne, Regen}, {hoch, niedrig}) \nonumber \\
                  & + & P({Sonne, Regen}, {hoch, hoch}) \nonumber
\end{eqnarray}
anschaulich sollte ein Gedanke nach unserer Probe daher erzeugt
werden. Die Berechnung von $P(O|\lambda)$ gem\"{a}{\ss} originaler
Definiton kann ziemlich gro{\ss} sein, man betracht im diesem Fall
den Rechenaufwand auf $O(N^T)$. Gibt es Methode, um diesen Schlechte
Fall zu verbessern? In den folgenden Abschnitten werden wir konkrete
darauf eingehen.

\subsubsection{Drei klassische Problemstellungen bei den
Anwendungen} Es gibt drei grundlegende Probleme, die gel\"{o}st
werden m\"{u}ssen, damit das Hidden Markov-Modell in der Real-Welt
bei verschiedenen Anwendungen n\"{u}tzlich ist. hier finde ich noch
ein sinnvolles Online-Tutorium \cite{HmmOnline} f\"ur alle
Interessanten vor.
\begin{enumerate}
  \item Gegeben sei die Beobachtungsfolge $O = O_1O_2{\ldots}O_T$
  und ein Modell $\lambda = (A, B, \pi)$, wie berrechnet man die
  Wahrscheinlichkeit $P(O|\lambda)$?
  \item Wie bestimmt man eine Zustandsfolge $Q = q_1q_2{\ldots}q_T$,
  die eine gegebene Beobachtungsfolge $O = O_1O_2{\ldots}O_T$ zu
  gegebenem Modell $\lambda = (A, B, \pi)$ am besten erkl\"{a}rt?
  \item Wie pa{\ss}t man die Modellparameter $\lambda = (A, B, \pi)$
  an, wenn nur die Beobachtungsfolge bekanntgegeben ist, um die
  Wahrscheinlichkeit $P(O|\lambda)$ zu maximieren?
\end{enumerate}
Die Wahrscheinlichkeit einer Reihenfolge von \"{U}berg\"{a}ngen
herauszufinden ist eine n\"{u}tzliche Sache, da wir bald sehen, aber
es ist auf keinen Fall die einzige Sache, die wir tun m\"{o}chten.
Um die Wahrscheinlichkeit einer Reihenfolge von Beobachtungen zu
finden,wird gekennzeichnet als \emph{\textbf{Evaluation}} und kann
in der Vorw\"{a}rts- und R\"{u}ckw\"{a}rts- Richtung gerechnet
werden (d.h. vorw\"{a}rts von der ersten Beobachtung arbeiten oder
von der letzten Beobachtung zur\"{u}ck zu arbeiten).\\[0.3cm]
Nachdem das oben genannte Problem gel\"{o}st worden war, im
allgemeinen k\"{o}nnen wir noch nicht absichern, welche Reihenfolge
der Zust\"{a}nde f\"{u}r eine gegebene Reihenfolge von Beobachtungen
vorgenommen wird, Im allgemeinen ist das beste, dass wir tun
k\"{o}nnen, die wahrscheinlichste Zustandflugbahn f\"{u}r eine
gegebene Reihenfolge von Beobachtungen zu sch\"{a}tzen. Dieses
Problem wird h\"{a}ufig als \emph{\textbf{Decodieren}} gekennzeichnet.
\\[0.3cm]
Eine andere allgemeine Anforderung ist, die Wahrscheinlichkeiten zu
erlernen, die mit \"{U}berg\"{a}ngen im System verbunden sind, durch
eine Repr\"{a}sentativtraining seine passende Reihenfolge gegeben
werden anstatt seine \"{U}bergangswahrscheinlichkeiten direkt
gegeben werden. Die Idee ist, das Raum von
\"{U}bergangswahrscheinlichkeiten zu finden, der die
Wahrscheinlichkeit der Training-Reihenfolge maximiert. Dieses ist
das \emph{\textbf{Lernproblem}}.

\subsubsection{Forward- und Backward-Algorithmus}
Die Wahrscheinlichkeit der Beobachtungen $O$ f\"{u}r eine
spezifische Zustandreihenfolge $Q$ ist:
\begin{center}
  \begin{eqnarray}
       P(O|Q, \lambda) & = & \prod_{t=1}^{T}P(O_t|Q_t, \lambda) \nonumber \\
                       & = & b_{q_1}(O_1)(\times)b_{q_2}(O_2){\ldots}{b_{q_T}(O_T)}
  \end{eqnarray}
\end{center}
und die Wahrscheinlichkeit der Zustandreihenfolge ist:

  \begin{equation}
  P(O|\lambda) = \pi_{q_1}a_{q_1q_2}a_{q_2q_3}{\ldots}a_{q_{T-1}q_T}
  \end{equation}

die Wahrscheinlichkeit einer Beobachtungssequenz bei vorgegebenem
Modell ist die Wahrscheinlichkeit f\"{u}r das Auftreten einer
Beobachtungssequenz bei allen moglichen Hintergrundsequenzen, die
sich zur 1.8 Gleichung expandieren l\"{a}sst.
\begin{eqnarray}
P(O|\lambda) & = & \sum_{alle Q}P(O|Q,\lambda)P(Q|\lambda)\\
             & = & \sum_{q_1,q_2,\ldots,q_T}\pi_{q_1}b_{q_1}
             (O_1)a_{q_1q_2}b_{q_2}(O_2)\nonumber \\
             &   & \ldots a_{q_{T-1}q_T}b_{q_T}(O_T)
\end{eqnarray}
also die Forward-Variable wird so definiert:

  \begin{equation}
  \alpha_t(i) = P(O_1,O_2,\ldots,O_t, q_t = s_i | \lambda)
  \end{equation}

\paragraph{Forward Rekursion} \ \\
\begin{center}
\begin{figure}
  \includegraphics[width=0.5\textwidth]{bilder_wei/forward.png}\\
  \caption{Forward-Rekursion}
\end{figure}
\end{center}
1) Initialisierung:

  \begin{equation}
  \alpha_1(i) = P(O_1,q_1 = s_i | \lambda) = \pi_ib_i(O_1),
  1{\leq}i{\leq}N
  \end{equation}

Die Gesamtwahrscheinlichkeit, Zustand $s_i$ im Zeitpunkt $1$ zu
erreichen, ist die Anfangswahrscheinlichkeit f\"{u}r $s_i$
multipliziert mit der Wahrscheinlichkeit, dass $O_1$ ausgegeben
wird.\\[0.3cm]
2) Induktion:

  \begin{equation}
  \alpha_{t+1}(j) = \sum_{i=1}^{N}\alpha_t(i)a_{ij}b_j(O_{t+1}),
  1{\leq}t{\leq}T-1, 1{\leq}j{\leq}N
  \end{equation}

Die Gesamtwahrscheinlichkeit, Zustand sj im Zeitpunkt t+1 zu
erreichen, ist die Summe der Wahrscheinlichkeiten von einem
beliebigen Zustand $s_i$ in Zustand $s_j$ zu kommen unter Ausgabe
des n\"{a}chsten Symbols $O_{t+1}$.\\[0.3cm]
3) Terminierung:

  \begin{equation}
  P(O|\lambda) = \sum_{i=1}^{N}\alpha_T(i)
  \end{equation}\\
Die Gesamtwahrscheinlichkeit der Realisierung ist die Summe der
Wahscheinlichkeiten, zum Zeitpunkt $T$ in einen beliebigen Zustand
zu kommen. Daher ist der Rechenaufwand auf $N^2T$ reduzierbar. also
wir k\"{o}nnen die Backward-Rekursion analog machen. Die Backward
Rekursion wird in der L\"{o}sung zum Problem $3$ verwendet und ist
nicht f\"{u}r das Problem $1$ notwendig.


\paragraph{Backward Rekursion} \ \\
Wir definieren zuerst die Backward-Variable:

  \begin{equation}
  \beta_t(i) = P(O_{t+1},O_{t+2},\ldots,O_T | q_t = s_i , \lambda)
  \end{equation}

1) Initialisierung:

  \begin{equation}
  \beta_T(i) = 1, 1{\leq}i{\leq}N
  \end{equation}

2) Induktion:

  \begin{equation}
  \beta_t(j)=\sum_{j=1}^{N}\beta_{t+1}(j)a_{ij}b_i(O_{t+1}),
  1{\leq}i{\leq}N, t = T-1, T-2, \ldots, 1
  \end{equation}

3) Terminierung:

  \begin{equation}
  P(O_1,O_2,\ldots,O_T) = \sum_{i=1}^{N}\beta_1(i)\pi_ib_i(O_1)
  \end{equation}

\begin{center}
\begin{figure}
  \includegraphics[width=0.6\textwidth]{bilder_wei/backward.png}\\
  \caption{Backward-Rekursion}
\end{figure}
\end{center}

\subsubsection{Viterbi-Algorithmus}
Die Frage welche Hintergrundsequenz optimal bei gegebener
Beobachtungssequenz und Modell ist, besch\"{a}ftigt sich damit, die
korrekte Zustandsabfolge zu finden. Zum zweiten Problem ist mit
Hilfe des Viterbi-Algorithmus l\"{o}sbar, wobei der $P(Q,O|\lambda)$
maximiert.\\[0.3cm]
Der Viterbi-Algorithmus ist eine Methode aus dem Gebiet der
Dynamischen Programmierung. Die Idee war, dass $\delta_t(i)$ die
hochste Wahrscheinlichkeit durch einen Suchpfad zum Zeitpunkt $n$
beschreibt. Dabei werden die ersten $n$ Beobachtungen gezahlt und
$\delta_t(i)$ landet schliesslich im Zustand $s_i$.

  \begin{equation}
  \delta_t(i) = \max_{q_1, q_2,\ldots, q_{t-1}} P(q_1, q_2,\ldots, q_t=i,
  O_1,O_2,\ldots,O_t|\lambda
  \end{equation}

Durch Induktion hat man die Beziehung $\delta_{t+1}(j)=[\max_i
\delta_t(i)a_{ij}]b_i(O_{t+1})$, Um die Zustandsfolge wieder zu
gewinnen, speichert man auch gleichzeitig das Argument, das die
$\delta_{t+1}(j)$ f\"{u}r jedes $t$ und $j$ jeweils maximiert, in
ein Feld $\Psi_t(j)$
\paragraph{Der gesamte Optimierungsvorgang} \ \\
1) Initialisierung:
\begin{center}
\begin{eqnarray}
\delta_1(i) & = & \pi_ib_i(O_i),1{\leq}i{\leq}N \\
\Psi_t(i)   & = & 0
\end{eqnarray}
\end{center}
2) Induktion:
\begin{eqnarray}
\delta_t(j) & = & \max_{1{\leq}i{\leq}N }[\delta_{t-1}(i)a_{ij}]b_j(O_t),2{\leq}t{\leq}T, 1{\leq}j{\leq}N \\
\Psi_t(i)   & = & \arg\max_{1{\leq}i{\leq}N}[\delta_{t-1}(i)a_{ij}]
,2{\leq}t{\leq}T, 1{\leq}j{\leq}N
\end{eqnarray}
3) Terminierung:
\begin{center}
\begin{eqnarray}
     P^{\star} & = & \max_{1{\leq}i{\leq}N } [\delta_T(i)]\\
 q_{t}^{\star} & = & \arg\max_{1{\leq}i{\leq}N }[\delta_T(i)]
\end{eqnarray}
\end{center}
4) Optimale Zur\"uckverfolgerung der Zustandsfolge:

  \begin{equation}
  q_{t}^{\star} = \Psi_{t+1}(q_{t+1}^{\star}),
  t=T-1, T-2, \ldots, 1
  \end{equation}

\begin{center}
\begin{figure}
  \includegraphics[width=0.6\textwidth]{bilder_wei/viterbi.png}\\
  \caption{Viterbi-Decoder}
\end{figure}
\end{center}

\subsubsection{EM-Algorithmus}
Der EM-Algorithmus \footnote{Expectation-Maximization Algorithmus}
ist ein allgemeines Verfahren zur Bestimmung von Maximum-Likelihood
Sch\"{a}tzwerten von probabilistischen Modellen. Die Bezeichnung
"Algorithmus" ist eigentlich irref\"{u}hrend, da in der allgemeinen
Definition des Verfahrens keine genauen Anweisungen f\"{u}r
Rechenschritte gegeben werden, wie es der Begriff des Algorithmus
fordert, sondern nur eine allgemeine Beschreibung des Verfahrens und
seiner mathematischen Eigenschaften. F\"{u}r jedes Anwendungsgebiet
musst daher ein EM-Algorithmus erfunden werden. F\"{u}r Hidden
Markov-Models hei{\ss}t dieser Algorithmus "`Baum-Welch
Algorithmus"'.
\begin{center}
\begin{figure}
  \includegraphics[width=0.6\textwidth]{bilder_wei/B-W-Algo.png}\\
  \caption{Baum-Welch-Algorithmus}
\end{figure}
\end{center}
$\xi_t(i, j), 1{\leq}t{\leq}T; 1{\leq}i,j{\leq}N$ sei die
Wahrscheinlichkeit, dass der \"{U}bergang zwischen Zustand $s_i$ und
Zustand $s_j$ zur Zeit $t$ (mit Forward-und Backward-Variable
geschrieben) bei einer gegebenen Realisation $O$ genommen wird:
\begin{center}
\begin{eqnarray}
\xi_t(i, j) & = & P(q_t=s_i,q_{t+1}=s_j|O,\lambda)\\
            & = & \frac{\alpha_t(i)a_{ij}b_j(O_{t+1})\beta_{t+1}(j)}
            {\sum_{i=1}^{N} \sum_{j=1}^{N}\alpha_t(i)a_{ij}b_j(O_{t+1})\beta_{t+1}(j)}
\end{eqnarray}
\end{center}
Weiterhin ist $\gamma_i(t) = \sum_{j=1}^{N}\xi_t(i,j)$ die
Wahrscheinlichkeit, dass Zustand $i$ zum Zeitpunkt $t$ bez\"uglich
$O$ erreicht wird.\\[0.3cm]
Im Estimation-Schritt werden nun die Erwartungswerte f\"{u}r die
Anzahl der \"{U}berg\"{a}nge pro Kante berechnet:
\begin{itemize}
  \item $\sum_{t=1}^{T-1} \gamma_i(t)$ ist die erwartete Anzahl von
  \"{U}berg\"angen aus Zustand $s_i$ bei Realisierung $O$.
  \item $\sum_{t=1}^{T-1} \xi_t(i,j)$ ist die erwartete Anzahl von
  \"{U}berg\"{a}ngen von Zustand $s_i$ nach $s_j$ bei Realisierung $O$.
\end{itemize}
Im Maximization-Schritt werden nun die Modellparameter neu berechnet
anhand der Erwartungswerte:
\begin{itemize}
  \item \begin{equation}
          \overline{\pi_i}=\gamma_i(1)
        \end{equation}\\
  Die neuen Anfangswahrscheinlichkeiten sind die Wahrscheinlichkeiten,
  dass Zustand $s_i$ zum Anfang der Zustandssequenz bez\"{u}glich $O$
  auftritt.
  \item \begin{equation}
          \overline{a_{ij}}=\frac {\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \gamma_i(t)}
        \end{equation}\\
  Die neue Wahrscheinlichkeit f\"{u}r einen \"{U}bergang von Zustand
  $s_i$ nach Zustand $s_j$ ist die erwartete Anzahl der \"{U}berg\"{a}nge
  von $s_i$ nach $s_j$ dividiert durch die erwartete Gesamtzahl der
  \"{U}berg\"{a}nge aus $s_i$ durch die Normierung entsteht hier wieder
  eine Wahrscheinlichkeit $0{\leq}a_{ij}{\leq}1$.
  \item \begin{equation}
          \overline{b_i{k}}=\frac {\sum_{t=1}^{T} \gamma_i(t)\delta_{k,O_t}}
  {\sum_{t=1}^{T} \gamma_i(t)}
        \end{equation}\\
  $\delta_{k,O_t}$ ist wie folgt definiert:
  \begin{equation}
  \delta_{k,O_t}= \begin{cases}
  1; & k=O_t\\
  0; & sonst
  \end{cases}
  \end{equation}
  Die neue Wahrscheinlichkeit f\"{u}r die Ausgabe eines Symbols $k$ im Zustand
  $s_i$ ist die erwartete Anzahl im Zustand $s_i$ zu sein und dabei das Symbol
  $k = O_t$ auszugeben, dividiert durch die erwartete Anzahl, \"{u}berhaupt im
  Zustand $s_i$ zu sein.
\end{itemize}
Damit wurde ein neues Modell $\overline{\lambda} =
(\overline{A},\overline{B},\overline{\pi})$ berechnet. Wie f\"{u}r
den EM-Algorithmus allgemein gezeigt, gilt
$P(O|\overline{\lambda})\geq P(O|\lambda)$.

\subsubsection{Zeichenbasiertes NER mit Hidden Markov-Modellen}
In einem Zeichenstrom kann mittels eines HMMs Named Entity erkennt
und klassifiziert werden. Interessant ist der Ansatz vorallem
deswegen, weil er aufzeigt, wie wertvoll bereits Teilsequenzen von
Zeichen sein k\"{o}nnen f\"{u}r NER.\\[0.3cm]
Das Ziel ist, zu einem gegebenen Text automatisch alle W\"{o}rter
mit den zugeh\"{o}rigen Wortarten zu annotieren. Wie beschrieben
kann ein HMM diese Aufgabe l\"{o}sen, wenn seine Parameter $(A, B,
\pi)$ richtig gesetzt sind. Ein HMM muss also trainiert werden,
indem man mithilfe eines vorgetaggten Textes die Parameter so
anpa{\ss}t, dass das HMM f\"{u}r die Wortfolgen in diesem Text die
richtigen Wortartfolgen mit m\"{o}glichst geringer Fehlerrate
ausgibt.\\[0.3cm]
Als Beispiel nehmen wir an, dass man die W\"{o}rtern eines Textes
ihre Wortarten zuweisen m\"{o}chte. Alles was vorliegt, ist ein Text
als eine Folge von W\"{o}rtern. Einen solchen Text kann man in
Ann\"{a}herung als eine Folge von zuf\"{a}lligen Ereignissen
interpretieren, zwar dass auf eine Wortart mit einer bestimmten
Wahrscheinlichkeit eine andere Wortart folgt, und f\"{u}r jede
Wortart dann mit einer bestimmtenWahrscheinlichkeit ein konkretes
Wort generiert wird. Betrachtet man den Text als Ergebnis des
gesamten Zufallsexperiments, so ist die Abfolge der W\"{o}rter
erkennbar, nicht mehr die Folge der Wortarten, die die W\"{o}rter
generierte.\\[0.3cm]
Ein Text kann also als ein Zufallsexperiment mit einer Menge von
Zufallsvariablen ${O_1,\ldots,O_T, q_1,\ldots,q_T}$ gesehen werden.
Die Werte der $O_i$ ist die Folge der beobachtbaren Daten (die
Realisierung), hier sind die einzelnen W\"{o}rter. Die Werte der
$q_i$ sind die versteckten Daten, n\"{a}mlich die zu den W\"{o}rtern
geh\"{o}rigen Wortarten.\\[0.3cm]
Die zugrundeliegende Verteilung ist also eine gemeinsame Verteilung
der Menge von Zufallsvariablen $\{O_1,\ldots,O_T ,$ $q_1,\ldots,q_T
\}$. Mit Hilfe des Hidden Markov-Modells  k\"{o}nnen solche
Verteilungen modellieren.\\[0.3cm]
Der Aufbau des HMM's wird schon erl\"{a}utert. Pro Zustand, welcher
vom HMM durchlaufen wird, wird ein Zeichen generiert bzw.
ausgegeben. Jeder Zustand wird durch ein Tupel bestehend aus Klasse
(Person, Ort, Organisation), welche den Offset im aktuellen Wort
angibt, identifiziert. Es gibt z.B. einen Zustand (Ort, 2) in
welchem die Emission des dritten Zeichens aller NE vom Typ 'Ort'
vorgenommen wird. Ein spezieller Endzustand (Ort, L) wird f\"{u}r
das Leerzeichen (Wortgrenze) zwischen zwei W\"{o}rtern verwendet.
Ferner wird eine Outputmodell der Form
$P(v_k|v_{k-1}{\ldots}v_{k-N+1}, s_k)$ benutzt, wobei ck das
aktuelle Zeichen und $s_k$ der aktuelle Zustand ist. Die Anzahl
Zust\"{a}nde pro Klasse ist beschr\"{a}nkt auf  N 'regul\"{a}re'
Zust\"{a}nde und den Endzustand.
\begin{center}
\begin{figure}
  \includegraphics[width=0.6\textwidth]{bilder_wei/ner mit hilfe des hmms.png}\\
  \caption{NER mit Hilfe des HMMs}
\end{figure}
\end{center}

\subsubsection{Statistische Modelle jenseits des HMMs}
Local-Berechnung-Methoden(Forward- und Backward- ,
Viterbi-Algorithmus) erleichtern die Analyse von gro{\ss}en
Datenmengen, wenn eine Sch\"{a}tzung von
Emissionswahrscheinlichkeiten vorhand ist. Der EM-Algorithmus ist
eine gute Wahl, wenn schnelle und nicht so pr\"{a}zise Ergebnisse
gefordert sind.
\begin{itemize}
  \item HMM sind f\"{u}r die Klassifikation und
  Modellbildung insbesondere von Zeitreihen gut geeignet.
  \item Durch das Modell erh\"{a}lt man viele Informationen
  \"{u}ber die modellierte Signalquelle.
\end{itemize}
Trotz erfolgreicher Eins\"{a}tze der einschl\"{a}gigen
HMM-Modellierungswerkzeuge in etlichen symbolverarbeitenden
KI-Anwendungen unterliegt das traditionelle Hidden Markov-Model
einer Reihe offenkundiger Schwachstellen und Einschr\"{a}nkungen:
\begin{itemize}
  \item das endliche Zustandsinventar f\"{u}hrt zu dem endlichen Ged\"{a}chtnis
  \item die fixe Abh\"{a}ngigkeitsstruktur der Zustandsvariablen
  \item die eindimensionale Organisation der Ausgabedaten
  \item insbesondere seine implizit exponentielle Zustandsverweildauer
\end{itemize}
welche in den nachkommden Abschnitte zur Vorstellung einiger
Variationen des Themas HMM gab: Maximum Entropy Markov Models,
Conditional Random Fields.




%bla bla bla siehe Abschnitt \ref{ir}
%wie schon in \cite{Joachims/2002a} behandelt.
