\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}


\newenvironment{proof}{\noindent{\bf Proof:}}{\qed\bigskip}
\newenvironment{proof_sketch}{\noindent{\bf Sketch of Proof}\hspace*{1em}}{\qed\bigskip}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{claim}{Claim}
\newtheorem{fact}{Fact}
\newtheorem{definition}{Definition}
\newtheorem{assumption}{Assumption}
\newtheorem{observation}{Observation}
\newtheorem{example}{Example}
\newcommand{\qed}{\rule{7pt}{7pt}}

\parskip=2ex

\parindent=0ex

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

\def\eqruleii#1#2#3{{\footnotesize
\begin{tabbing}
#1 \hspace{.2in} \= #2 \\
		 \> \parbox{1.5in}{\noindent \hrule \mbox{}} \\
		 \> #3
\end{tabbing}}}


\def\eqruleiiii#1#2#3#4#5{{\footnotesize
\begin{tabbing}
#1 \hspace{.2in} \= #2 \\
                 \> #3 \\
                 \> #4 \\
		 \> \parbox{1.5in}{\noindent \hrule \mbox{}} \\
		 \> #5
\end{tabbing}}}

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


{\bf Problem 1.} 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.  

The sequence $S$ of internal states must have the form
$$S = a_{i}^{k_1} b^{k_2} a_{j}^{k_1} b^{k_2} a_{l}^{k_1} b^{k_2}$$
without loss of generality we may assume that $a_{i} = a_1$,
$a_{j} = a_2$, and $a_{l} = a_3$.

then
$$Pr(S \wedge D|\lambda) = Pr(S |\lambda) Pr(D |\lambda \wedge S) = Pr(S |\lambda)$$
since $Pr(D |\lambda \wedge S) = 1$
$$Pr(S |\lambda) = \frac{1}{4} A_{1}^{k_1-1} (1 - A_1) B^{k_2 -1} \frac{(1-B)}{3}A_{2}^{k_3-1} (1 - A_2) B^{k_4 -1} \frac{(1-B)}{3}A_{3}^{k_5-1} (1 - A_3) B^{k_6 -1}$$
simplifying a little
$$Pr(S |\lambda) = \frac{1}{36}B^{k_2+k_4+k_6 - 3} (1-B)^2 A_{1}^{k_1-1} (1 - A_1) A_{2}^{k_3-1} (1 - A_2) A_{3}^{k_5-1} (1 - A_3)$$

Now to find the values of $A_1$, $A_2$, $A_3$, and $B$ that maximize 
$P_r(S \wedge D|\lambda)$ set
$$\frac{\partial Pr(S |\lambda)}{\partial A_1} = c (k_1 -1) A_{1}^{k_1-2} (1- A_1) - c A_{1}^{k_1-1} = 0$$
where $c = \frac{1}{36}B^{k_2+k_4+k_6 - 3} (1-B)^2 A_{2}^{k_3-1} (1 - A_2) A_{3}^{k_5-1} (1 - A_3)$

and solving for $A_1$ we get $A_1 = \frac{k_1 -1}{k_1}$.  Similarly we get
$A_2 = \frac{k_3 -1}{k_3}$, $A_3 = \frac{k_5 -1}{k_5}$, and $B = \frac{k_2+k_4+k_6 -3}{k_2+k_3+k_6-1}$.

If you tried to solve for 
$$Pr(S |\lambda \wedge D) = \frac{Pr(D|\lambda \wedge S ) Pr(S |\lambda)}{Pr(D |\lambda)} = \frac{Pr(S|\lambda)}{Pr(D |\lambda)} $$ 
And this is the value you need to
maximize.  But because of the denominator term this turns out to be a
rather big expression which doesn't simplify nicely when it is
differentiated.

{\bf Part b.}  The property that transitions among the $a$ states have probability $0$
is {\bf stable}.
Baum-Welch reestimation recomputes the transition probabilities from the expected number 
of transitions between the states $a_1$, $a_2$, and $a_3$.  Since the probability of
such transitions is always $0$, the expected value is $0$ and the new probability
for these transitions will remain $0$.

{\bf Part c.}  The property that the output symbols are generated deterministically
is {\bf stable}.
Again, Baum-Welch reestimation recomputes the probability of an output
symbol in a state from the number of times it sees this output symbol when in
this state.  Since it will never see an a in state $b$ or a b in any $a$ state,
these probabilities will not be changed.

{\bf Part d.} As long as not all the $A_i$ are equal there are many
strings for which Baum-Welch reestimation would move to a
model where the transition from the $b$ to an $a$ state does not give
the $a$ states equal probability. Intuitively, you want to break the symmetry
between $a$ states with a string that has many transitions from b to a short string
of a's and one to a long string of a's.

For example, consider the string ``bababababaaaaaaaaaaaaaababa''.  The
transitions to the $a$ state with least $A_i$ will have a high
probability of transition from b , and the one with largest $A_i$ will
have a low probability of transition from b after reestimation.

If all the $A_i$ are equal there is no way to break the symmetry.

{\bf Problem 2.}  

We are looking for a square in an 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}}$.

{\bf part a.}
If we assume that the square in the image is rotated about the origin and
then translated.  Call this pose $\beta$, where $\beta = \tuple{x,\;y,\;\Delta}$
and $\Delta$ is a (counter clockwise) rotation angle.

Now, we need to match features in the image (angles or corners) with
features of the model.  To match we first compute how each model
corner looks under the pose $\beta$, i.e.
$$P(M_i,\;\beta) = \tuple{x_p,\;y_p,\;\Theta_p,\;,\Psi_p}$$.
If we interpret $\beta$ as a rotation about the origin followed
by a translation then we have
$$x_p = x_{M_i}\cos \Delta_\beta - y_{M_i} \sin \Delta_\beta + x_\beta$$
$$y_p = - x_{M_i}\sin \Delta_\beta + y_{M_i} \cos \Delta_\beta + y_\beta$$
$$\Theta_p = \Theta_{M_i} + \Delta$$
$$\Psi_p = \Psi_{M_i} + \Delta$$

{\bf Part b.}
Now assume that a set of angles is generated by running a feature
detection algorithm (an angle detector) on the 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$.  

The interpretation $\Gamma$ specifies that $Y_i$ was generated
from $P(\Gamma_i,\;\beta)$ by adding Gaussian noise.  The probability of
seeing a given value for $Y_i$ in the image is equal to the probability
of generating the noise that precisely maps $P(\Gamma_i,\;\beta)$ to the value $Y_i$,
i.e., it is the probability that the noise value is precisely $Y_i - P(\Gamma_i, \beta)$.
Here we assume that the
Gaussian noise consists of real numbers and hence we are dealing with
a contiuous probability density function.  Since the noise in each component
is indendent it suffices to specify the probability density function for each
component of the noise independently (the joint probability density function is just
the product of the pdfs for the component values.)  

Hence if $\Gamma_i = M_i$ we have
$$P_r(x_i|\Gamma,\;\beta) = \frac{1}{\sqrt{2\pi\sigma_p}}e^{\frac{-(x-x_p)^2}{2\sigma^2_p}}$$
$$P_r(y_i|\Gamma,\;\beta) = \frac{1}{\sqrt{2\pi}\sigma_p}e^{\frac{-(y-y_p)^2}{2\sigma^2_p}}$$
$$P_r(\Theta_i|\Gamma,\;\beta) = \frac{1}{\sqrt{2\pi}\sigma_a}e^{\frac{-(\Theta-\Theta_p)^2}{2\sigma2_a}}$$
$$P_r(\Psi_i|\Gamma,\;\beta) = \frac{1}{\sqrt{2\pi}\sigma_a}e^{\frac{-(\Psi-\Psi_p)^2}{2\sigma^2_a}}$$
where $\tuple{x_i,\;y_i,\;\Theta_i,\;\Psi_i}$ is $P(\Gamma_i,\;\beta)$ as defined
in part a, and $\sigma_p$ and $\sigma_a$ are standard deviations.  
Note that this formula can be written in the form 
$$P_r(Y_i) = N_{\Psi}(Y_i - P(\Gamma_i, \beta))$$
where $N_\Psi$ is the multivariate normal distribution specified by
a covariance matrix $\Psi$ (this is the formula in the Wells paper).

If $\Gamma_i = \bot$, then $Pr(Y_i| \Gamma,\;\beta) = \frac{1}{(2\pi)^2 ImageArea}$

\end{document}  

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