\input psadobe
\documentstyle[12pt,epsf]{report}
\newcommand{\bigcenter}[1]{\begin{center} {\Large\bf #1} \end{center}}
\setlength{\oddsidemargin}{.25in}       
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}          
\setlength{\textheight}{8.5in}

\parskip=2ex

\parindent=0ex

\newcommand{\necpos}[1]{[\langle #1 \rangle]}

\input nofill.tex
\input texcom.tex

\begin{document}
\centerline{\bf \large 6.824 Artificial Intelligence, Fall 1992}
\centerline{\bf \large Problem Set 3}
\medskip
\medskip

\centerline{Due:  Beginning of class Wednesday, October 7}

{\bf Problem 1. (25 points)} This problem is on Hidden Markov Models.  Consider a
hidden Markov model $\lambda$ with four internal state $a_1$, $a_2$,
$a_3$ and $b$ and two external symbols $a$ and $b$.  We assume that
if the internal state is either $a_1$, $a_2$, or $a_3$ then the external
symbol is always $a$ and if the internal state is $b$
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$, $A_3$ and $B$. $A_1$ is the probability that when the
machine is in state $a_1$ then the next machine state remains $a_1$.
$A_2$, $A_3$ and $B$ are the analogous ``no change'' probabilities
for states $a_2$, $a_3$ and $b$ 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 from state $b$ to one of the $a$ states
all three $a$ states are equally likely.  Initially all four states are
equally likely.

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

{\bf Part b.}  State transitions between the states $a_1$, $a_2$ and $a_3$ are
not allowed in the above model.  Is this property stable under Baum-Welch reestimation?
In other words, if we use Baum-Welch reestimation to construct a new
model, will this new model allow transitions between different $a$ states?
Explain your answer.

{\bf Part c.}  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?


{\bf Part d.}  Describe a sequence of external
symbols such that Baum-Welch reestimation starting from the above model 
would move to a model where the transition from the $b$ to an $a$ state does not
give the $a$ states equal probability.  Explain your answer.

{\bf Problem 2.}  This problem is on the use of MAP in vision.  It would be a good idea to
read this problem before reading Well's paper since the example given here
might make the general formalism in the paper clearer.  Suppose that we
have ``features'' that are corners, i.e., places where two edges meet such as
that shown below.

\epsfxsize 2in
\centerline{\epsffile{/com/6.824/fall92/problem-sets/ps4-fig2.ps}}

A corner can be represented by four numbers $\tuple{x,\;y,\;\Theta,\;\Psi}$
as shown below (in the figure $\Theta$ and $\Psi$ are called angle1 and angle2).

\epsfxsize 2in
\centerline{\epsffile{/com/6.824/fall92/problem-sets/ps4-fig3.ps}}

Suppose that we are looking for a square in some image.
A square has four corners so we have a model vector
$$M\;=\;\{M_1,\;M_2,\;M_3,\;M_4\}$$ where each $M_i$ is a model corner
$\tuple{x_{M_i},\;y_{M_i},\;\Theta_{M_i},\;\Psi_{M_i}}$.
We will take a pose of the triangle to be a translation plus a rotation.
A pose can therefore be specified by three numbers $\tuple{x,\;y,\;\Delta}$
where $\Delta$ is a (counter clockwise) rotation angle.

{\bf part a.}  Give an expression for the angle $P(M_i,\;\beta)$ where $M_i$
is a model angle and $\beta$ is a pose as specified above. $P(M_i,\;\beta)$
consists of four numbers that specify how the model angle $M_i$ appears
under the pose $\beta$.

Now assume that a set of angles is generated by running a feature
detection algorithm (an angle detector) on an image.  Let
$\tuple{Y_1,\;\ldots,\;Y_n}$ be the set of angles detected in a given
image.  Each $Y_i$ consists of four numbers --- the four numbers that
specify an angle.  Let $\Gamma$ be the tuple
$\tuple{\Gamma_1,\;\ldots,\;\Gamma_n}$ where $\Gamma_i$ is an
interpretation of angle $Y_i$.  Each $\Gamma_i$ is one of
the four model angles $M_j$ or the special ``unassigned'' symbol
$\bot$.  We assume that if $\Gamma_i$ is $M_j$ then under pose $\beta$
we have that $Y_i$ is $P(M_j,\;\beta)$, as defined in part a, plus
Gaussian noise.  Assume that the noise in each of the four numbers
specifying $Y_i$ incorporates noise independent of the noise in the
other components and the noise in each component has zero mean and
variance $\sigma_p$ for noise in positions and $\sigma_a$ for noise
in angles.

{\bf Part b.}   Give an expression for
$$P_r(Y_i|\Gamma,\;\beta)$$ as a function of the three values specifying
$\beta$, the four values in the model angle $\Gamma_i$, and the noise
variances $\sigma_p$ and $\sigma_a$.  Your answer should be consistent with the equations
in Well's paper.

\end{document}