preliminaries.tex

A \emph{Markov Chain (MC)} $K = (S, p)$ consists of a finite set $S$ of
\emph{states} and a \emph{transition distribution} $p : S \times S
\rightarrow \bbfRU$ such that $\sum_{t \in S} p (s, t) = 1$ for every
$s \in S$.
A \emph{Hidden Markov Model (HMM)} $H = (K, \Obs, o)$ is a finite MC $K =
(S, p)$ with a finite set $\Obs$ of \emph{observations} and an
\emph{observation distribution} $o : S \times \Obs \rightarrow \bbfRU$
such that $\sum_{\obs \in \Obs} o (s, \obs) = 1$ for every $\obs \in
\Obs$. An HMM models a MC with incomplete information. Intuitively,
the states of HMMs are not observable. External observers do not know
the current state of an HMM. Instead, they have a state distribution
$\pi : S \rightarrow [0, 1]$ with $\sum_{s \in S} \pi (s) = 1$
to represent the likelihood of each state in HMMs.

Let $H = ((S, p), \Obs, o)$ be an HMM and $\pi$ an initial state
distribution. The HMM $H$ can be seen as a (randomized) generator for
sequences of observations. The following procedure generates
observation sequences of an arbitrary length:
\begin{enumerate}
\item $t \leftarrow 0$.
\item Choose an initial state $s_0 \in S$ by the initial state
  distribution $\pi$.
\item \label{hmm:repeat}
  Choose an observation $\omega_t$ by the observation distribution
  $o (s_t, \bullet)$.
\item Choose a next state $s_{t+1}$ by the transition distribution
  $p (s_t, \bullet)$.
\item $t \leftarrow t + 1$ and go to \ref{hmm:repeat}.
\end{enumerate}

Given an observation sequence $\overline{\omega} =
\omega_0\omega_1\cdots\omega_k$ and a state sequence $\overline{s} =
s_0s_1\cdots s_k$, it is not hard to compute the probability of
observing $\overline{\omega}$ along $\overline{s}$ on an HMM $H = ((S,
p), \Obs, o)$ with an initial state distribution $\pi$. Precisely,
\begin{align}
  \Pr (\overline{\omega}, \overline{s} | H)
  & = \Pr (\overline{\omega} | \overline{s}, H) \times \Pr(\overline{s}, H)
    \nonumber
  \\
  & = [o (s_0, \omega_0) \cdot \cdots \cdot
    \times o (s_k, \omega_k)] \times
      [\pi (s_0) \times p (s_0, s_1) \cdot \cdots
    \cdot p (s_{k-1}, s_k)]
    \nonumber
  \\
  & = \pi (s_0) o (s_0, \omega_0) \cdot
    p (s_0, s_1) o (s_1, \omega_1) \cdot \cdots \cdot
    p (s_{k-1}, s_k) o (s_k, \omega_k).
    \label{eqn:prob-obs-state}
\end{align}

Since state sequences are not observable directly, we would like to
compute in $\Pr (\overline{\omega} |
H)$. Using~(\ref{eqn:prob-obs-state}), we have
\[
  \Pr (\overline{\omega} | H) = \sum_{\overline{s} \in S^{k+1}}
  \Pr (\overline{\omega}, \overline{s} | H).
\]
But the summation has $|S|^{k+1}$ terms. An efficient method is to
compute the probability $\alpha_t (s)$ for the partial observation
sequence $\omega_0\omega_1\cdots\omega_t$ with the state $s$ at time
$t$~\cite{R:89:ATHMM}. Consider the following definition:
\begin{align}
  \alpha_0 (s) &= \pi(s) o (s, \omega_0)
  \label{hmm:basis}
  \\
  \alpha_{t+1} (s') &= \left[
                      \sum_{s \in S} \alpha_t (s) p (s, s')
                      \right]
                      o (s', \omega_{t+1}).
  \label{hmm:inductive}
\end{align}
Then $\Pr (\overline{\omega} | H) = \sum_{s \in S} \alpha_k (s)$.