% -*- mode: TeX -*-
\documentstyle[12pt]{article}

\input nofill.tex
\input texcom.tex

\parskip=2ex

\begin{document}

\centerline{\bf \huge 17. Hidden Markov Models}

\section{Problems}

\eject
{\bf Problem 2. (25 points)} This problem is on Hidden Markov Models.  Consider a
hidden Markov model $\lambda$ with four internal state $a_1$, $a_2$,
$b_1$ and $b_2$ and two external symbols $a$ and $b$.  We assume that
if the internal state is either $a_1$ or $a_2$ then the external
symbol is always $a$ and if the internal state is either $b_1$ or
$b_2$ then the external symbol is always $b$.  We also assume that the
state transition probability matrix is determined by four numbers
$A_1$, $A_2$, $B_1$ and $B_2$. $A_1$ is the probability that when the
machine is in state $a_1$ then the next machine state remains $a_1$.
$A_2$, $B_1$ and $B_2$ are the analogous ``no change'' probabilities
for states $a_2$, $b_1$ and $b_2$ respectively.  If the machine does
change state it must change from an ``a'' state to a ``b'' state or
vice versa, e.g., there is no chance of a transition from $a_1$ to
$a_2$.  When the machine changes state the two possible successor
states are equally likely.

{\bf Part a. (15 points)}  Let $D$ be a sequence of $k_1$ $a$'s followed by $k_2$ $b$'s
followed by $k_3$ $a$'s and then $k_4$ $b$'s.  Give a sequence $S$ of 
$k_1 + k_2 + k_3 + k_4$ internal states and values for $A_1$, $A_2$, $B_1$,
and $B_2$ such that $P_r(D|\lambda \wedge S)$ is maximized ($\lambda$
is the hidden Markov model determined by $A_1$, $A_2$, $B_1$ and $B_2$).

\vspace{3in}

{\bf Part b. (5 points)}  Is the hidden Markov model you specified in part a stable
under Baum-Welch reestimation?  In other words, if we start with this
model $\lambda$ and then compute a new model usng the Baum-Welch reestimation
technique, is the new model the same as the old model.  Explain your answer.

\vspace{2in}

{\bf Part c. (5 points)}  The model you constructed in part a generates the external
symbols deterministically --- only one external symbol is possible for a
given internal state.  Is this property preserved by Baum-Welch reestimation?
In other words, if we use Baum-Welch reestimation to construct a new
model, does this new model generate external symbols deterministically?
Explain your answer.

\vspace{2in}

{\bf Problem 1.} Consider a Markov model with two internal states $s_0$ and $s_1$.
We assume that whatever the internal state (whether it is
$s_0$ or $s_1$) the transition probability matrix of
the Markov model is such that the probability that the next state is different
from the current state is $P_c$ (the probability of change).
We assume that $P_c < \frac{1}{2}$, i.e., the system is more likely to stay
in the same state than to change states.
Note that the probability of remaining in the same state is
$1-P_c$.  Now suppose this Markov model is part of a Hidden Markov process
with two possible output tokens, 0 and 1.  Let $P_a$ (for probability of
agreement) be the probability that the output symbol is 1 when the
internal state is $s_1$ and also the probability that the output
symbol is 0 when the internal state is $s_0$.  We assume that $P_a > \frac{1}{2}$.
Intuitively, the internal state $s_1$ favors the output symbol 1
and the internal state $s_0$ favors the output symbol 0.
Assume that the internal states $s_0$ and $s_1$ are equally likely
in the initial state and the first output token corresponds to the
initial state.
Now Consider a bit string $D$ that is an observed sequence of
of output 1s and 0s.  Suppose that $D$ is $n$ 0s followed by $k$ 1s.
We wish to find the sequence $S$ of internal states which maximizes
$P_r(S|D)$.  Depending on the value of $n$, $k$,
$P_c$ and $P_a$ there are three possible correct answers.
Give three values for $S$ such that for some values of $n$, $k$, $P_c$ and $P_a$
(subject to the constraint $P_a > \frac{1}{2}$ and $P_c < \frac{1}{2}$) the
expression $P_r(S|D)$ is maximized.  For each answer give conditions
on $n$, $k$, $P_c$ and $P_a$ which guarantee that $P_r(S|D)$ is maximized
for that answer.
Your conditions should cover all possibilties, i.e., any values
of $n$, $m$, $P_a$ and $P_c$ with $P_c < \frac{1}{2}$ and $P_a > \frac{1}{2}$
should satisfy the conditions of one of your answers.

{\bf Problem 2.}  This problem concerns the hidden Markov process described
in problem 1. Let $P_1$ be the probability that the first
data value is 0.  Let $P_2$ be the probability that the second
data value is 0 given that the first data value is 0.  Let $P_3$
be the probability that the third data value is 0 given that the
first two values are 0.  Note that the probability that a data
sequence starts with three 0s is the product $P_1P_2P_3$.  Give a value for
$P_1$ and put a check in the appropriate true/false box for each of the
hypothetical relations given below.  Give
an explanation of your answers.

\hspace{.5in}$P_1\;\; =\;\;\; \mbox{\tt }$

\begin{tabular}{|l|l|l|} \hline
~ & True & False \\ \hline
$P_2 = P_1$ & & \\ \hline
$P_2 > P_1$ & & \\ \hline
$P_3 = P_2$ & & \\ \hline
$P_3 > P_2$ & & \\ \hline
\end{tabular}

\bibliographystyle{named}

\bibliography{/home/c2/dam/biblio/master}

\end{document}