\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amsbsy}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{verbatim}
\usepackage[left=0.5in,right=0.5in,top=1in,bottom=1in]{geometry}
\begin{document}

\renewcommand{\thesection}{Problem \arabic{section}:}
\renewcommand{\theenumi}{\alph{enumi}}
\addtolength{\belowcaptionskip}{-5mm}

\def\x{{\bf x}}
\title{\underline{Problem Set 2}}
\author{MAS 622J/1.126J: Pattern Recognition and Analysis}
\date{Due: 5:00 p.m. on October 12}
\maketitle

\noindent [Note: All instructions to plot data or write a program
should be carried out using Matlab.  In order to maintain a reasonable level of consistency and simplicity
we ask that you do not use other software tools.]

If you collaborated with other members of the class, please write their names at the end of the assignment. Moreover, you will need to write and sign the following statement: ``In preparing my solutions, I did not look at any old homeworks, copy anybody's answers or let them copy mine."





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Discriminability and ROC [20 points]} 
Please download the datasets (dataset1.txt, dataset2.txt, dataset3.txt, dataset4.txt) from the course website.   Each dataset includes 1-D data samples from two classes $w_1$ and $w_2$. 
The first column and the second column of each dataset specify 1000 samples from class $w_1$ and 1000 samples from class $w_2$, respectively.

\begin{enumerate}
\item For each dataset, compute the discriminability $d' = \;\frac{{\left| {\mu _2  - \mu _1 } \right|}}{{\sqrt {\sigma _1^2  + \sigma _2^2 } }}$ where $\mu_1$ and $\sigma_1$ are the mean and standard deviation of the distribution of class $w_1$, and $\mu_2$ and $\sigma_2$ are the mean and standard deviation of the distribution of class $w_2$.  

\noindent\textbf{Solution:}
Please refer to the Matlab code for (b). 
Approximately,
For dataset1:  $\mu_1$ $\simeq $ 10,  $\mu_2$ $\simeq $ 12, $\sigma_1$ $\simeq $ 1, $\sigma_2$ $\simeq $ 1, $d'$ $\simeq $ 1.39\\
For dataset2:  $\mu_1$ $\simeq $ 10,  $\mu_2$ $\simeq $ 12, $\sigma_1$ $\simeq $ 4, $\sigma_2$ $\simeq $ 1, $d'$ $\simeq $ 0.46\\
For dataset3:  $\mu_1$ $\simeq $ 10,  $\mu_2$ $\simeq $ 12, $\sigma_1$ $\simeq $ 1, $\sigma_2$ $\simeq $ 4, $d'$ $\simeq $ 0.45\\
For dataset4:  $\mu_1$ $\simeq $ 10,  $\mu_2$ $\simeq $ 12, $\sigma_1$ $\simeq $ 4, $\sigma_2$ $\simeq $ 4, $d'$ $\simeq $ 0.31

\item Now we compute the ROC curve for each dataset.  Please plot four ROC curves in the same figure.  To do this, we approximate  ${\bf P_{TP} = P(x>x^* | x } \in w_2)$ by ${\bf N(x>x^* | x } \in w_2) /1000$, and ${\bf P_{FP} = P(x>x^* | x } \in w_1)$ by ${\bf N(x>x^* | x } \in w_1) /1000$.   Here,  for $i=$1 or 2, ${\bf N(x>x^* | x } \in w_i)$ is denotes the number of samples in class $w_i$ whose value is greater than ${\bf x^*}$.  Note that ${\bf N}$ doesn't denote a normal distribution!

\noindent\textbf{Solution:}
Changing the classifier value (${\bf x^*}$) from $-\infty$ to $\infty$, we can plot the ROC curve for each dataset.  Note that when ${\bf x^*}$ = $-\infty$, ${\bf P_{TP} = 1 \text{ and } P_{FP} = 1}$ (corresponding to the uppermost/rightmost position in the ROC curve), and when ${\bf x^*}$ = $\infty$, ${\bf P_{TP} = 0 \text{ and } P_{FP} = 0}$ (corresponding to the lowermost/leftmost position in the ROC curve).

\verbatiminput{"ROC_sol.m"}

\begin{center}
\includegraphics[width=10cm]{ROC.png}
\end{center}

\item For each dataset, plot the two {\it approximated} probability density functions.  Note that the probability density function is the derivative of the cumulative density function.  (Do NOT just approximate distributions by Gaussians and draw those approximated Gaussians in this problem.)   {\it Hint:} Use the same method we use in (b) to get the cumulative distribution.  This is called {\it Monte Carlo} method.  Also, note that the derivative (i.e., probability density function $p(x)$) relates to the increment of the cumulative density function $P_{X}(x)$. That is, $p(x) = \Delta P_{X}(x) / \Delta x$.

\noindent\textbf{Solution:}
%\verbatiminput{"draw_distributions_all.m"}

\begin{center}
\includegraphics[width=14cm]{distributions.png}
\end{center}


\item How does the discriminability relate to the ROC curve?  

\noindent\textbf{Solution:}

First, comparing dataset1 ($d'$ = 1.39) with dataset4 ($d'$ = 0.31), we can see that the two distributions in dataset1 are more discriminable than the ones in dataset4 (See the distribution plot in (c)).  Also, from the ROC plot in (b), we find that better performance (here, meaning higher ${\bf P_{TP}}$ and lower ${\bf P_{FP}}$ with the optimal classifier location) is achieved on dataset1, compared with dataset4.  In general, for two gaussian distributions, as $d'$ becomes bigger, ${\bf P_{TP}} - {\bf P_{FP}}$ becomes bigger (Refer to the problem 5 (a) in our Problem Set 2).  

Second, comparing dataset2 ($d'$ = 0.46) with dataset3 ($d'$ = 0.45), we can see that the discriminability of the two distributions in dataset2 is almost the same as that of the ones in dataset3 (See the distribution plot in (c)).  Also, from the ROC plot in (b), we find that ROC curves of dataset3 and dataset4 have very different characteristics although the two have similar $d'$ values.  Note that depending on the shapes of two distributions (in dataset2, the distribution with higher mean has lower variance, but in dataset3, the distribution with higher mean has higher variance), the characteristic of the corresponding ROC curve is determined.  Note that for each dataset, when the change of the classifier value (${\bf x^*}$) happens at around the mean of the distribution with lower variance, the ROC curve (${\bf P_{TP}}$ for dataset2, ${\bf P_{FP}}$ for dataset3) radically changes.



\end{enumerate}



\section{(DHS 2.6) Optimal Decision Boundaries  [20 points]}
A Spanish campany called Goorrel has launched an application to recognize important e-mails ($\omega_1$) vs unimportant e-mails ($\omega_2$.)  The company is using two secret features such
that their training data is well approximated by two Gaussians:
\begin{align*}
p(\textbf{x}|\omega_1)&\sim\mathcal{N}(\mu_1,\Sigma_1)\\
p(\textbf{x}|\omega_2)&\sim\mathcal{N}(\mu_2,\Sigma_2)
\end{align*}
where $\mu_1=[0\text{ }0]^T$, $\mu_2=[5\text{ }0]^T$, $\Sigma_1=\text{I}$, and $\Sigma_2=\left[\begin{array}{rl}4&0\\0&4\end{array}\right]$,
where $\text{I}$ is the identity matrix.
\begin{enumerate}
\item Plot the one-sigma ellipses for these two classes in the place $\textbf{x}=[x_1\text{ }x_2]^T$.

\noindent\textbf{Solution:}
The one sigma ellipses are circles of radii $1$ and $2$ respectively (see Figure \ref{fig:circ}.)

%\noindent\includegraphics[width=5in]{ps3-1a.pdf}
\begin{figure}[h]
\center
\includegraphics[width=3in]{circ.pdf}
\caption{One sigma ellipses}
\label{fig:circ}
\end{figure}

(MATLAB code is at the end of the problem)

\item The company finds that choosing a threshold at $x_1=3$ perfectly separates the
training examples they have; thus, they propose that this should be the best classifier.
Show them an expression, in terms of $\textbf{x}$, which can improve their classifier with respect to minimizing the Bayes probability of error.
Assume that unimportant emails are three times as likely as important emails.

\noindent\textbf{Solution:}
Using discriminant functions for each class, we have:
\begin{equation*}
g_i(\textbf{x})=\textbf{x}^T W_i\textbf{x}+\textbf{w}_i^T +w_i,
\end{equation*}
where
\begin{align*}
W_i&=-\frac{1}{2}\Sigma_i^{-1},\\
\textbf{w}_i&=\Sigma_i^{-1}\boldsymbol{\mu}_i,\text{ and}\\
w_i&=\frac{1}{2}\boldsymbol{\mu}_i^T\Sigma_i^{-1}\boldsymbol{\mu}_i - \frac{1}{2}\ln{|\Sigma_i|} + \ln{P(\omega_i)}.
\end{align*}
Because email from class $\omega_2$ is three times as likely as email from class $\omega_1$, we have:
\begin{align*}
P(\omega_2)&=3P(\omega_1),\text{ and}\\
P(\omega_1)+P(\omega_2)&=1.\text{ Resulting in}\\
P(\omega_1)&=\frac{1}{4},\text{ and}\\
P(\omega_2)&=\frac{3}{4}.
\end{align*}
Then, plugging in our values to the discriminant equations, we have:
\begin{align*}
g_1(\textbf{x}) &=            \textbf{x}^T(-\frac{1}{2}\Sigma_1^{-1})                                        \textbf{x}+     (\Sigma_1^{-1}                                         \boldsymbol{\mu}_1)^T                                 \textbf{x} - \frac{1}{2}\boldsymbol{\mu}_1^T                          \Sigma_1^{-1}                                         \boldsymbol{\mu}_1                           - \frac{1}{2}\ln{|\Sigma_i|}                                       + \ln{P(\omega_1)}\\
                &=-\frac{1}{2}\textbf{x}^T             \left[\begin{array}{cc}1&0\\0&1\end{array}\right]^{-1}\textbf{x}+\left(\left[\begin{array}{cc}1&0\\0&1\end{array}\right]^{-1}\left[\begin{array}{c}0\\0\end{array}\right]\right)^T \textbf{x} - \frac{1}{2}\left[\begin{array}{c}0\\0\end{array}\right]^T\left[\begin{array}{cc}1&0\\0&1\end{array}\right]^{-1}\left[\begin{array}{c}0\\0\end{array}\right] - \frac{1}{2}\ln{\left|\begin{array}{cc}1&0\\0&1\end{array}\right|} + \ln{\frac{1}{4}}\\                
                &=-\frac{1}{2}(x_1^2+x_2^2) + \ln{\frac{1}{4}} 
\end{align*}
and
\begin{align*}
g_2(\textbf{x})&=\textbf{x}^T(-\frac{1}{2}\Sigma_2^{-1})\textbf{x}+(\Sigma_2^{-1}\boldsymbol{\mu}_2)^T\textbf{x} - \frac{1}{2}\boldsymbol{\mu}_2^T\Sigma_2^{-1}\boldsymbol{\mu}_2 - \frac{1}{2}\ln{|\Sigma_2|} + \ln{P(\omega_2)}\\
  &=-\frac{1}{2}\textbf{x}^T             \left[\begin{array}{cc}4&0\\0&4\end{array}\right]^{-1}\textbf{x}+\left(\left[\begin{array}{cc}4&0\\0&4\end{array}\right]^{-1}\left[\begin{array}{c}5\\0\end{array}\right]\right)^T \textbf{x} - \frac{1}{2}\left[\begin{array}{c}5\\0\end{array}\right]^T\left[\begin{array}{cc}4&0\\0&4\end{array}\right]^{-1}\left[\begin{array}{c}5\\0\end{array}\right] - \frac{1}{2}\ln{\left|\begin{array}{cc}4&0\\0&4\end{array}\right|} + \ln{\frac{3}{4}}\\ 
               &=-\frac{1}{8}(x_1^2+x_2^2) + \frac{5}{4}x_1 - \frac{25}{8} - \frac{1}{2}\ln{16} + \ln{\frac{3}{4}}
\end{align*}
Now, using the decision criteria, $g_1(\textbf{x})>g_2(\textbf{x})$, to decide when to choose category $\omega_1$, we get:
\begin{align*}
-\frac{1}{2}(x_1^2+x_2^2) + \ln{\frac{1}{4}} &> -\frac{1}{8}(x_1^2+x_2^2) + \frac{5}{4}x_1  -\frac{25}{8} - \frac{1}{2}\ln{16} + \ln{\frac{3}{4}}\\
-\frac{3}{8}(x_1^2+x_2^2) -  \frac{5}{4}x_1 &>  -\frac{25}{8} - \frac{1}{2}\ln{16} + \ln{\frac{3}{4}} - \ln{\frac{1}{4}}\\
x_1^2+x_2^2  + \frac{10}{3}x_1 &< \frac{8}{3} (\frac{25}{8} + \frac{1}{2}\ln{16} - \ln{\frac{3}{4}} + \ln{\frac{1}{4}})\\
(x_1+ \frac{5}{3})^2+x_2^2 &< \frac{8}{3} (\frac{25}{8} + \frac{1}{2}\ln{16} - \ln{\frac{3}{4}} + \ln{\frac{1}{4}}) + \frac{25}{9}\\
(x_1+ \frac{5}{3})^2+x_2^2 &< 3.45^2
\end{align*}
So, if $\textbf{x}$ is within the circle described by the above equation, then we should decide $\omega_1$.


\item The shape of this optimal decision boundary is:
\begin{itemize}
\item a line
\item a parabola
\item a hyperbola
\item a circle
\item an ellipse
\item none of the above (explain)
\end{itemize}
Be sure to justify your answer.

\noindent\textbf{Solution:}
\emph{a circle}: The decision region is a circle with mean, $\mu_d=[-\frac{5}{3} 0]^T$, and radius, $r=3.45$ (see Figure \ref{fig:db}.)
This makes sense because both of the Gaussian distributions are circular, so dividing the two distributions, such as in the following form of the discriminant function
\begin{equation}
g(\textbf{x})=\ln{\frac{p(\textbf{x}|\omega_1)}{p(\textbf{x}|\omega_2)}} + \ln{\frac{P(\omega_1)}{P(\omega_2)}}
\end{equation}
must also be circular.

\begin{figure}[h]
\center
\includegraphics[width=3in]{db.pdf}
\caption{Decision Boundary ($\lambda_{21} = 1$)}
\label{fig:db}
\end{figure}

\item If Gorrel accidently misses relevant e-mails, then this will be terrible for the users.  The company estimates this error will cost them twenty times as much as the cost of missclasifying unimportant e-mails (there's no cost to choosing correctly in either case.)  Describe qualitatively
how this changes your result above.  Make a sketch of the change (it doesn't have to
be precisely plotted). Justify your answer.

\noindent\textbf{Solution:}
Previously, we had implicitely assumed an equal cost for making a misclassification error, such that $\lambda_{12}=1$, $\lambda_{21}=1$, $\lambda_{11}=0$, and $\lambda_{22}=0$.
Now, we must now minimize the cost function with, $\lambda_{12}=1$, $\lambda_{21}=20$, $\lambda_{11}=0$, and $\lambda_{22}=0$.  Using the minimum-risk decision rule, we can see how things change when the risk is no longer equal for each type of misclassification:
\begin{align*}
(\lambda_{21}-\lambda_{11})p(\textbf{x}|\omega_1)P(\omega_1) &> (\lambda_{12}-\lambda_{22})p(\textbf{x}|\omega_2)P(\omega_2)\\
20p(\textbf{x}|\omega_1)\frac{1}{4} &> p(\textbf{x}|\omega_2)\frac{3}{4}\\
\frac{20}{3} p(\textbf{x}|\omega_1) &> p(\textbf{x}|\omega_2)
\end{align*}
We can see that this new decision relationship makes decisions favor $\omega_1$ much more than previously.  The shape of the decision boundary will now be a larger circular decision region within which we should choose $\omega_1$ (see Figure \ref{fig:db2}.)

The new decision boundary looks as follows:
\begin{figure}[h]
\center
\includegraphics[width=3in]{db2.pdf}
\caption{New Decision Boundary ($\lambda_{21} = 20$)}
\label{fig:db2}
\end{figure}

\end{enumerate}

The MATLAB code that generates all of the figures is as follows:

\verbatiminput{ps3_1.m}


\section{Principal Component Analysis [10 points]}

Consider the covariance matrix for a Gaussian with mean = (0,0) and variance~=~$\sigma^2 \times I_2$ where $\sigma^2$ is a positive constant, and $I_2$ is a 2 $\times$ 2 identity matrix.


\begin{enumerate}
\item  What are the two principle components for this matrix? What are their eigenvalues?

\noindent\textbf{Solution:}
In order to compute the principal components, we have to find the eigenvalues ($\lambda$) and eigenvectors ($\mathbf{v}$) of the covariance matrix ($\Sigma$ = $\sigma^2 \times I_2$) after mean ($\mu$) centering the data for each attribute. Since $\mu = 0$, we can find the eigenvalues by solving:
\[\det(\Sigma - \lambda I) = \mathbf{0}\]
\[\det\begin{bmatrix} \sigma^2-\lambda & 0\\0 & \sigma^2-\lambda \end{bmatrix} = (\sigma^2-\lambda)^2 = 0\]

Therefore, $\lambda_1$ = $\lambda_2$ = $\sigma^2$ and $\mathbf{v}$ will be any vector that satisfies:
\[\begin{bmatrix} \sigma^2 & 0\\0 & \sigma^2 \end{bmatrix}\times \mathbf{v} = \sigma^2 \times \mathbf{x}\]
To ensure orthonormality of the components, we select the following vectors $\mathbf{v}_1~=~\begin{bmatrix}1 & 0\end{bmatrix}^{\rm T}$ and $\mathbf{v}_2~=~\begin{bmatrix}0 & 1\end{bmatrix}^{\rm T}$.


\item  Given a data point (x,y) from this distribution, what is the reconstructed data using the projection onto the first principal component of this matrix?

\noindent\textbf{Solution:}
Given the properties of our covariance matrix, both components (i.e. $\mathbf{v}_1$ and $\mathbf{v}_2$) are equally important. If we project our data point $\mathbf{p}$ into $\mathbf{v}_1$ we obtain:

\[\mathbf{v}_1^{\rm T} \cdot (\mathbf{p} - \mu)= \begin{bmatrix} 1 & 0 \end{bmatrix}\begin{bmatrix} x \\ y \end{bmatrix} = x\]

If we reconstruct our data point, we obtain:
\[\mathbf{\hat{p}} = \mathbf{v}_1 \times x + \mu= \begin{bmatrix} 1 \\ 0 \end{bmatrix} \times x = \begin{bmatrix} x \\ 0 \end{bmatrix}\]
\item For this reconstructed value, what is the expected value of the reconstruction error (squared error between the true value and reconstructed value).

\noindent\textbf{Solution:}
The squared error between the true value (p) and the reconstructed value ($\mathbf{\hat{p}}$) is:
\[SE = \sum_{i=1}^2 (\mathbf{\hat{p}}_i-\mathbf{p}_i)^2\ = \mathbf{y}^2\]

Give the properties of our covariance matrix, the expected value of SE is:
\[\operatorname{E}(SE) = \operatorname{E}(\mathbf{y}^2) = \operatorname{Var}(\mathbf{y}) + \operatorname{E}(\mathbf{y})^2 = \sigma^2 + 0 = \sigma^2\]


\end{enumerate} 



\section{EigenFaces [30 points]}
In this exercise we provide a dataset\footnote{This is a small set of the CMU MultiPIE dataset (http://www.multipie.org)} of face images (450x400 pixels) to explore the concept of eigenfaces and some of its applications. Please include MATLAB code and images to support your answers. 

\begin{enumerate}
\item Find the eigenfaces of the dataset and show the first three components. The images can be loaded by using the helper function ``[X] = load\_imgs('training');'" in MATLAB. (Hint: svd(X,0))

\noindent\textbf{Solution:}
Figure \ref{fig:ps3eigfaces} shows the first three principal components. As we can see, they represent the variance of the images (e.g. beard, glasses). The MATLAB code can be found at the end of the problem.
\begin{figure}[h]
\center
\includegraphics[width=3in]{ps3eigfaces.pdf}
\caption{First three principal components}
\label{fig:ps3eigfaces}
\end{figure}

\item Reduce the dimensionality of the images by projecting them onto a lower dimensional space. How many basis are you using? Justify your answer. 

\noindent\textbf{Solution:}
In order to select the basis we can look at the energy associated to their eigenvalues. Figure \ref{fig:ps3energy} shows the normalized eigenvalues and a standard threshold of 0.95. Note that with these basis we reduce from 180000 (450 x 400) to just 24 dimensions.

\begin{figure}[h!]
\center
\includegraphics[width=3in]{ps3energy.pdf}
\caption{Normalized eigenvalues and 0.95 energy threshold}
\label{fig:ps3energy}
\end{figure}

\item We received a new image but we lost some of its information. How do you suggest to automatically fix it? Explain your solution as well as the result. (``[X] = load\_imgs('corrupted');'")

\noindent\textbf{Solution:}
As we saw in class, we can find the missing information by projecting and then restoring the image. Figure \ref{fig:ps3reconst} shows the image before and after this process.

\begin{figure}[h!]
\center
\includegraphics[width=2.5in]{ps3reconst.pdf}
\caption{(Left) Original image, (right) reconstructed image}
\label{fig:ps3reconst}
\end{figure}


\item We received another image but this time we do not know the name of the person. Use the eigenfaces to perform face recognition. For the sake of simplicity, you can report the closest image in the training set instead of the name of the person. (``[X] = load\_imgs('testing');'")

\noindent\textbf{Solution:}
To recognize the face we can find the closest match in the training data. To do so, we project the image onto a lower dimensional space and compare its coefficients ($y_{test} = W^T (I-\mu_X$) to the ones of the training data ($Y_{train} = W^T (X - \mu_X)$). Figure \ref{fig:ps3match} shows the closest match using Euclidean distance.

\begin{figure}[h!]
\center
\includegraphics[width=2.5in]{ps3match.pdf}
\caption{(Left) Testing image, (right) Closest match}
\label{fig:ps3match}
\end{figure}


\item Suggest a different way to use eigenfaces.

\noindent\textbf{Solution:}
In class we saw that they are useful for outlier detection and data compression. 


The MATLAB code for all of the previous questions is as follows:

\verbatiminput{main.m}

%\item In order to analyze the difference between PCA and Fisher Linear Discriminant, find the basis and reduce the dimensionality of the images located in the folder ``pca\_lda". Which one seems to be better? Why? (Hint: You can use two or three basis to visualize the information.)
%
%\noindent\vspace{5mm}\textbf{Solution:}
%Coming soon...

%\noindent\vspace{5mm}\textbf{Solutions:}
%
%Figure \ref{} shows the first principal components. As we can see, they represent the variance of the images. Figure \ref{} shows the energy values for the eigenvectors
%The following MATLAB code include all of the computations:


%\iterm Using two different faces (load_data2.m) show a scatter plot of the classes in 2D and 3D
%\noindent\vspace{5mm}\textbf{Solution:}
\end{enumerate} 

\section{Hidden Markov Models [20 points]}
%%%%%%%%%%%%%%%%%%%%%%
% QUESTION:
We have two 2-state Hidden Markov Models, where both states have two possible output symbols A and B: \\
\begin{figure}[h]
\center
\includegraphics[width=3in]{hmm.jpg}
\caption{Two HMMs}
\label{fig:circ}
\end{figure}
The output probabilities are given by: 
\begin{equation*}
\text{Model 1:  b$_{1}$(A)=0.85 \ \ \  b$_{1}$(B)=0.15 \ \ \ b$_{2}$(A)=0.4 \ \ \  b$_{2}$(B)=0.6 }
\end{equation*}
\begin{equation*}
\text{Model 2:  b$_{1}$(A)=0.2 \ \ \  b$_{1}$(B)=0.8 \ \ \ b$_{2}$(A)=0.1 \ \ \  b$_{2}$(B)=0.9 }
\end{equation*}
The initial probabilities are given by:
\begin{equation*}
\text{Model 1: $\pi_{1}$ = 0.75 \ \ $\pi_{2}$ = 0.25  }
\end{equation*}
\begin{equation*}
\text{Model 2: $\pi_{1}$ = 0.5 \ \ $\pi_{2}$ = 0.5}
\end{equation*}

\begin{enumerate}
\item For Model 1, what is the probability of an observation sequence \{ B A B \} being generated? \\ \\ 
%%%%%%%%%%%%%%%%%%%%%%
 \textbf{SOLUTION}: \\ \\
P( \{ B A B \} $|$ M$_{1}$ ) \\ 

\begin{center} 
\begin{tabular}{|  l | c | r | } 
\hline State Sequence & Probability Calculation for State Sequence & Total \\ 
\hline 1 1 1 & 0.75 * 0.15 * 0.7 * 0.85 * 0.7 * 0.15 & 0.007  \\ 
\hline 1 1 2 & 0.75 * 0.15 * 0.7 * 0.85 * 0.3 * 0.6 & 0.012 \\ 
\hline 1 2 2 & 0.75 * 0.15 * 0.3 * 0.4 * 1 * 0.6 & 0.0081 \\
\hline 2 2 2 & 0.25 * 0.6 * 1 * 0.4 * 1 * 0.6 & 0.036 \\
\hline -- & Sum & 0.0631 \\  \hline
\end{tabular} 
\end{center}
The probability of the observed sequence given model 1 is: 0.0631.  I.e. the sum of the probabilities of all the ways that this sequence could have occurred in model 1.

\item For Model 1, given that this HMM produced an observation sequence \{ B A B \}, what is the most likely sequence of hidden states that led to those observations? \\ \\
%%%%%%%%%%%%%%%%%%%%%%
% SOLUTION:
 \textbf{Solution}: \\ 
Look at for max row in the table above:\\ \\
2 2 2 is the most probable sequence of hidden states to produce the observed sequence given model 1.


\item Which model is more likely to produce the observation sequence \{ B A B \}? \\ \\
%%%%%%%%%%%%%%%%%%%%%%
% SOLUTION:
 \textbf{Solution}: \\
\begin{center} 
\begin{tabular}{|  l | c | r | } 
\hline State Sequence & Probability Calculation for State Sequence & Total \\ 
\hline 1 1 1 & 0.5 * 0.8 * 0.6 * 0.2 * 0.6 * 0.8 & 0.023  \\ 
\hline 1 1 2 & 0.5 * 0.8 * 0.6 * 0.2 * 0.4 * 0.9 & 0.0173 \\ 
\hline 1 2 2 & 0.5 * 0.8 * 0.4 * 0.1 * 1 * 0.9 & 0.0144 \\
\hline 2 2 2 & 0.5 * 0.9 * 1 * 0.1 * 1 * 0.9 & 0.0405 \\
\hline -- & Sum & 0.0952 \\  \hline
\end{tabular} 
\end{center}
Model 2 is more likely to produce the observed sequence as the sum of probabilities of all the possible ways that the sequence could occur is greater for model 2.
\end{enumerate}


\end{document}
