\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 4}}
\author{MAS 622J/1.126J: Pattern Recognition and Analysis}
\date{Due: 5:00 p.m. on October 22}
\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{Expectation Maximization and Missing Data [20 points]} 

Consider data, $
D = \left\{ {\left( \begin{array}{l}
 1 \\ 
 3 \\ 
 \end{array} \right),\left( \begin{array}{l}
 4 \\ 
 5 \\ 
 \end{array} \right),\left( \begin{array}{l}
 2 \\ 
 * \\ 
 \end{array} \right)} \right\}
$, sampled from a two-dimensional (separable) distribution, 
$p(x_1 ,x_2 ) = p_{x_1}(x_1 )p_{x_2}(x_2 )$, with
\\\\
$~~~~~~~~~~~ p_{x_1}(x_1 ) = \left\{ \begin{array}{l}
 \frac{1}{{\theta _1 }}e^{ - x_1 /\theta _1 } \quad {\rm{if}} ~ x_1  \ge 0 \\ 
 0\quad \quad \quad \quad {\rm{  otherwise}} \\ 
 \end{array} \right.
$ ~~~~~~~ $
p_{x_2}(x_2 ) = \left\{ \begin{array}{l}
 \frac{1}{{\theta _2 }}\quad \quad {\rm{if  }} ~ 0 \le x_2  \le \theta _2  \\ 
 0\quad \quad ~ {\rm{  otherwise}} \\ 
 \end{array} \right.
$ \\\\
and a missing feature value, *.
\begin{enumerate}

\item What can you infer from $\theta_2$ by looking at $D$?

\noindent\vspace{5mm}\textbf{Solution:}
$\theta_2$ is necessarily greater or equal to 5 because $0 < x_{12} = 3 < x_{22} = 5 \le \theta_{2}$. 

\item Start with an initial estimate $
\underline{\theta}^0=\left( \begin{array}{l}
 3 \\ 
 6 \\ 
 \end{array} \right)
$ and analytically calculate $Q(\underline{\theta}; \underline{\theta}^0)$.  This is the {\it estimate} step in the EM algorithm.

\noindent\vspace{5mm}\textbf{Solution:}

The probability of one sample can be determined by:
\begin{align*}
 p({\bf{x}}{\rm{|} \underline{\theta}} ) = p(x_1 ,x_2 | \underline{\theta}) 
&= p_{x1}(x_1 | \underline{\theta}) p_{x_2}(x_2 | \underline{\theta}) \\ 
&= \left\{ \begin{array}{l}
 \left( {\frac{1}{{\theta _1 }}e^{ - x_1 /\theta _1 } } \right)\left( {\frac{1}{{\theta _2 }}} \right)\quad {\rm{if ~ }}x_1  \ge 0\;{\rm{and ~ 0}} \le x_2  \le \theta _2  \\ 
 0\quad \quad \quad {\rm{ ~~~~~~~~~~~ otherwise}} \\ 
 \end{array} \right. \\ 
  &= \left\{ \begin{array}{l}
 \frac{1}{{\theta _1 \theta _2 }}e^{ - x_1 /\theta _1 } \quad {\rm{if ~ }}x_1  \ge 0\;{\rm{and  ~ 0}} \le x_2  \le \theta _2  \\ 
 0\quad \quad \quad {\rm{ ~~~~~~ otherwise}} \\ 
 \end{array} \right. \\ 
 \end{align*}

%With our initial parameters, our distribution becomes:
%
%
%\begin{align*}
% p({\bf{x}}{\rm{|}}\underline{\theta}^0 ) &= p(x_1 ,x_2 |\underline{\theta}^0  ) \\ 
%  &= \left\{ \begin{array}{l}
% \frac{1}{{15}}e^{ - x_1 /3} \quad {\rm{if ~ }}x_1  \ge 0\;{\rm{and ~ 0}} \le x_2  \le 6 \\ 
% 0\quad \quad \quad {\rm{ ~~ otherwise}} \\ 
% \end{array} \right. \\ 
% \end{align*}
Formulating the log likelihood of the data and marginalizing over the possible values of the unknown data:

\begin{align*}
 Q(\underline{\theta};\underline{\theta}^0 ) &= E_{x_{32} } [\ln p({\bf{x}}_g ,{\bf{x}}_b ; \underline{\theta})|\underline{\theta}^0 ;D_g ] \\ 
  &= \int_{ - \infty }^\infty  {\left[ {\sum\limits_{k = 1}^2 {\ln p({\bf{x}}_k |\underline{\theta})}  + \ln p({\bf{x}}_3 |\underline{\theta})} \right]} p(x_{32} |x_{31}  = 2;\underline{\theta}^0 )dx_{32}  \\ 
  &= \sum\limits_{k = 1}^2 {\ln p({\bf{x}}_k |\underline{\theta})}  + \int_{ - \infty }^\infty  {\ln p\left( {\left[ \begin{array}{l}
 2 \\ 
 x_{32}  \\ 
 \end{array} \right]|\underline{\theta}} \right)\frac{{p\left( {\left[ \begin{array}{l}
 2 \\ 
 x_{32}  \\ 
 \end{array} \right]|\underline{\theta}^0 } \right)}}{{\int_{ - \infty }^\infty  {p\left( {\left[ \begin{array}{l}
 2 \\ 
 x'_{32}  \\ 
 \end{array} \right]|\underline{\theta}^0 } \right)} dx'_{32} }}} dx_{32}  \\ 
 \end{align*}

Note that $x_{31}$ and $x_{32}$ are independent with each other. Thus, 
\[
\begin{array}{c}
 p\left( {\left[ \begin{array}{l}
 2 \\ 
 x_{32}  \\ 
 \end{array} \right]|\underline{\theta}^0 } \right) = p_{x_1 } \left( {x_{31}  = 2|\underline{\theta}^0 } \right)p_{x_2 } (x_{32} |\underline{\theta}^0 ), \\ 
 \int_{ - \infty }^\infty  {p\left( {\left[ \begin{array}{l}
 2 \\ 
 x'_{32}  \\ 
 \end{array} \right]|\underline{\theta}^0 } \right)} dx'_{32}  = p_{x_1 } \left( {x_{31}  = 2|\underline{\theta}^0 } \right)\int_{ - \infty }^\infty  {p_{x_2 } (x'_{32} |\underline{\theta}^0 )} dx'_{32}  = p_{x_1 } \left( {x_{31}  = 2|\underline{\theta}^0 } \right) \\ 
 \end{array}
\]

Therefore,
\[
Q(\underline{\theta};\underline{\theta}^0 ) = \sum\limits_{k = 1}^2 {\ln p({\bf{x}}_k |\underline{\theta})}  + \int_{ - \infty }^\infty  {\ln p\left( {\left[ \begin{array}{l}
 2 \\ 
 x_{32}  \\ 
 \end{array} \right]|\underline{\theta}} \right)p_{x_2 } (x_{32} |\underline{\theta}^0 )} dx_{32} 
\]



Note that $p\left( {\left[ \begin{array}{l}
 2 \\ 
 x_{32}  \\ 
 \end{array} \right]|\underline{\theta}} \right)$ is different than zero if $ 0 \le x_{32} \le \theta_2$, and $p_{x_2 } (x_{32} |\underline{\theta}^0 )$ is different than zero if $ 0 \le x_{32} \le \theta_2 ^0 = 6$.

Therefore, $p\left( {\left[ \begin{array}{l}
 2 \\ 
 x_{32}  \\ 
 \end{array} \right]|\underline{\theta}} \right)$$p_{x_2 } (x_{32} |\underline{\theta}^0 )$  is different than zero between [0, min($\theta_2$ , 6)]


\[
\sum\limits_{k = 1}^2 {\ln p({\bf{x}}_k |\underline{\theta})}  = \ln \frac{1}{{\theta _1 \theta _2 }}e^{ - 1/\theta _1 }  + \ln \frac{1}{{\theta _1 \theta _2 }}e^{ - 4/\theta _1 }  = 2\ln \frac{1}{{\theta _1 \theta _2 }} - \frac{5}{{\theta _1 }}
\]
 
\begin{align*}
 \int_{ - \infty }^\infty  {\ln p\left( {\left[ \begin{array}{l}
 2 \\ 
 x_{32}  \\ 
 \end{array} \right]|\underline{\theta}} \right)p_{x_{32} } \left( {x_{32} |\underline{\theta}^0 } \right)} dx_{32} = \int_0^{\min (\theta _2 ,6)} {\left( {\ln \frac{1}{{\theta _1 \theta _2 }}e^{ - 2/\theta _1 } } \right)} \left( {\frac{1}{6}} \right)dx_{32}  \\ 
 = \left\{ \begin{array}{l}
 \theta _2 \frac{1}{6} \left( {\ln \frac{1}{{\theta _1 \theta _2 }} - \frac{2}{{\theta _1 }}} \right)\quad {\rm{~if~  min(}}\theta _2 ,6) = \theta _2 ,\quad {\rm{where~ 5 }} \le \theta _2  < 6\; \\ 
 \ln \frac{1}{{\theta _1 \theta _2 }} - \frac{2}{{\theta _1 }}\quad {\rm{~~~~~~~~~~if~  min(}}\theta _2 ,6) = 6,\quad {\rm{where~ }}\theta _2  \ge 6\quad \quad \quad {\rm{  }} \\ 
 \end{array} \right. \\ 
 \end{align*}

Finally,

\begin{align*}
 Q(\underline{\theta};\underline{\theta}^0 ) &= \sum\limits_{k = 1}^2 {\ln p({\bf{x}}_k |\underline{\theta})}  + \int_{ - \infty }^\infty  {\ln p\left( {\left[ \begin{array}{l}
 2 \\ 
 x_{32}  \\ 
 \end{array} \right]|\underline{\theta}} \right)p_{x_{32} } \left( {x_{32} |\underline{\theta}^0 } \right)} dx_{32}  \\ 
  &= \left\{ \begin{array}{l}
 2\ln \frac{1}{{\theta _1 \theta _2 }} - \frac{5}{{\theta _1 }} + \frac{1}{6}\theta _2 \left( {\ln \frac{1}{{\theta _1 \theta _2 }} - \frac{2}{{\theta _1 }}} \right)\quad {\rm{where~ 5 }} \le \theta _2  < 6\; \\ 
 3\ln \frac{1}{{\theta _1 \theta _2 }} - \frac{7}{{\theta _1 }}{\rm{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~where~ }}\theta _2  \ge 6\quad \quad \quad {\rm{  }} \\ 
 \end{array} \right. \\ 
 \end{align*}




\item Find the $\underline{\theta}$ that maximizes your $Q(\underline{\theta}; \underline{\theta}^0)$ -- the {\it maximization} step of the EM algorithm.

\noindent\vspace{5mm}\textbf{Solution:}

First,
\[
\frac{{\partial Q(\underline{\theta}; \underline{\theta}^0)}}{{\partial \theta _2 }} = \left\{ \begin{array}{l}
  - \frac{2}{{\theta _2 }} - \frac{1}{6}\left( {\frac{2}{{\theta _1 }} - \ln \frac{1}{{\theta _1 \theta _2 }}} \right) - \frac{1}{6}\quad {\rm{~~where ~5 }} \le \theta _2  < 6\; \\ 
  - \frac{3}{{\theta _2 }}\quad \quad {\rm{~~~~~~~~~~~~~~~~~~~~~~~~~~~~ where ~ }}\theta _2  \ge 6\quad \quad \quad {\rm{  }} \\ 
 \end{array} \right.
\]

Thus, $Q(\underline{\theta}; \underline{\theta}^0) < 0$ where $\theta_2 \ge 5$.   
(Note $\frac{2}{{\theta _1 }} - \ln \frac{1}{{\theta _1 \theta _2 }}$= $\frac{1}{{\theta _1 }} + (\frac{1}{{\theta _1 }}- \ln \frac{1}{{\theta _1 }}) + \ln \theta _2 > 0$ because $\frac{1}{\theta_1} >0$, $(\frac{1}{{\theta _1 }}- \ln \frac{1}{{\theta _1 }}) \ge 1$ and $\ln \theta_2 > 0$ where $\theta_1 > 0$ and $\theta_2 \ge 5$.)

Second, $Q(\underline{\theta};\underline{\theta}^0 )$ is continuous at $\theta_2 = 6$, because the two equations corresponding to the two intervals ($ 5 \le \theta_2 < 6$, $ \theta_2 \ge 6$) have the same value at $\theta_2 = 6$, which is $ 3\ln \frac{1}{{6 \theta _1 }} - \frac{7}{{\theta _1 }} $.

From these two facts, we can conclude that $Q(\underline{\theta};\underline{\theta}^0 )$ is a monotonically decreasing continuous function with respect to $\theta_2$. Thus, the maximum occurs when $\theta_2 = 5$.

To find the value of ${\theta _1}$ that maximizes $Q$ when $\theta_2 = 5$,
 $\frac{{\partial Q(\underline{\theta};\underline{\theta}^0 )}}{{\partial \theta _1 }} = 
 - \frac{2}{{\theta _1 }} + \frac{5}{{\theta _1 ^2 }} - \frac{5}{{6\theta _1 }} + \frac{10}{{6\theta _1 ^2 }} = 0$.  Thus, we find that  $\mathop {\arg \max }\limits_{\theta _1 } Q(\underline{\theta};\underline{\theta}^0 ) = \frac{40}{17}\quad$ (i.e.,$\quad \theta _1  = \frac{40}{17}$ and $\theta_2 = 5$).



\end{enumerate}



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




\section{Baum-Welch Algorithm and Discrete HMMs  [40 points]}

Download the datasets from the course webpage.  The datasets consist of training and testing sequences belonging to two classes. We assume the two HMMs for the two classes have the same configuration, i.e. the same number of states, zero transition probabilities and the number of output states.

 Implement the Baum-Welch algorithm for training a discrete HMM. Train HMMs with one, three, and five states with transition probabilities in a strictly left-to-right configuration (see the figure below for a two-state HMM in left-to-right configuration). The visible output has four possible states 0, 1, 2 or 3. 
 and
 
 
 \begin{figure}[ht]
\centering
\includegraphics[width=0.75\textwidth]{p3}
\caption{HMM in a left-to-right configuration}
\end{figure}


% 
%\begin{figure}[h]
%\center
%\includegraphics[width=3in]{p3.png}
%\caption{HMM in a left-to-right configuration}
%\end{figure}

 Repeat the following steps for each of the three HMM configurations with one, three, and five states:
 
 \begin{enumerate}
 \item Train two HMMs, one for each class of data. State very clearly the threshold you are using and the maximum number of iterations.  List the output probabilities and state transition probabilities of each HMM.
 \item Implement the Viterbi algorithm to decode each test sequence using both HMMs. Show the log probability of each test sequence using each HMM.
 \item Show the confusion matrix of the test set.
  \end{enumerate}
Include a complete listing of your source code. 

\noindent\vspace{5mm}\textbf{Solution:}

The MATLAB code for this problem can be downloaded from the course website. The code was developed by Ashish Kapoor (ash@media.mit.edu)
\footnote{
Copyright 2002 by the Massachusetts Institute of Technology. All rights reserved. Permission to use, copy, or modify this software and its documentation for educational and research purposes only and without fee is hereby granted, provided that this copyright notice and the original authors' names appear on all copies and supporting documentation.}.

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

\section{Bayes Networks [20 points]}
Consider the following Bayesian Network where the three events are $B$ (Burglary), $E$ (Earthquake) and $A$ (Alarm).   Assume that the three nodes are binary nodes that can take on the value $f$ (false) or $t$ (true).   

\begin{center}
\includegraphics[width=40mm]{cond_dep.png}
\end{center}

\noindent Here, $B$ and $E$ are marginally independent.  That is, $P(B, E) = P(B)P(E)$ (Note that this relation implies $P(B|E) = P(B)$ or $P(E|B) = P(E)$.)  Now we want to show $B$ and $E$ are conditionally dependent given $A$.  In other words, $P(B, E | A) \ne P(B|A) P(E|A)$.

\begin{enumerate}
\item Prove that the relation $P(B, E | A) \ne P(B|A) P(E|A)$ implies $P(B | E, A) \ne P(B|A)$.  Note that by the symmetry between $B$ and $E$, this also means $P(E | B, A) \ne P(E|A)$.\\

\noindent\vspace{5mm}\textbf{Solution:}
From $P(B,E|A) \ne P(B|A)P(E|A)$, we get the relation $\frac{{P(B,E|A)}}{{P(E|A)}} \ne P(B|A)$\\
Also, we know that $P(B|E,A)=\frac{{P(B,E|A)}}{{P(E|A)}}$ by Bayes' rule.\\
Therefore, $P(B|E,A) \ne P(B|A)$


\item First, we consider a very simple case.  Suppose $A$ = $B$ + $E$ where the + sign means ``Logical OR."  This means that $B$ and $E$ are independent deterministic causes of $A$.  
Construct the CPT (conditional probability table) for $P(A ~| B, E)$.  
 
\noindent\vspace{5mm}\textbf{Solution:}
\begin{tabular}{c | c}
$B$, $E$ & $P(A=f ~ | B,E)$, $P(A=t ~| B,E)$\\
\hline
$f, f$ &1 ~~~~~~~ 0 \\
$t, f$ &0 ~~~~~~~ 1 \\
$f, t$ &0 ~~~~~~~ 1 \\
$t, t$ &0 ~~~~~~~ 1 \\
\end{tabular}

\item For the obtained CPT above, prove that $P(B=t | A=t) =  P(B=t) / P(A=t)$.  Which is greater between $P(B=t | A=t)$ and $P(B=t)$?   What is the meaning of this?

\noindent\vspace{5mm}\textbf{Solution:}
$P(B = t|A = t) = P(A = t,B = t)/P(A = t)$ by Bayes' rule.\\
Now for $ P(A = t,B = t)$, \\
$\begin{array}{l}
 P(A = t,B = t) \\ 
  = \sum\limits_{E = t,f} {P(A = t,B = t,E)} {\rm{   ~~(by~marginalization)}} \\ 
  = \sum\limits_{E = t,f} {P(B = t)P(E)P(A = t|B = t,E)} {\rm{    ~~(from~the~graphical~model)}} \\ 
  = P(B = t)P(E = t)P(A = t|B = t,E = t) + P(B = t)P(E = f)P(A = t|B = t,E = f) \\ 
  = P(B = t)P(E = t) + P(B = t)P(E = f) \\ 
  = P(B = t)\left( {P(E = t) + P(E = f)} \right) \\ 
  = P(B = t) \\ 
 \end{array}$

Therefore, $P(B = t|A = t) = P(B = t)/P(A = t)$

Since $P(A=t) \le 1$, $P(B=t | A=t) \ge P(B=t)$

Note that $P(B=t)$ means your belief on $B=t$ (Burglary happened) without being given any information about $E$ and $A$.
However, $P(B=t | A=t)$ means your belief on $B=t$ (Burglary happened) when you know $A=t$ (Alarm happened).
Thus, $P(B=t | A=t) \ge P(B=t)$ means that your belief of $B=t$ (Burglary happend) increases when you know $A=t$ (Alarm happened).
 
\item For the obtained CPT above, prove that $P(A=t) = P(B=t) + P(E=t) - P(B=t) P(E=t)$.   If $P(B=t)$ and $P(E=t)$ are small, what happens to $P(B=t | A=t)$, compared with $P(B=t)$?

\noindent\vspace{5mm}\textbf{Solution:}
\[
\begin{array}{l}
 P(A = t) \\ 
  = \sum\limits_{B = t,f} {\sum\limits_{E = t,f} {P(A = t,B,E)} } {\rm{  }} \\ 
  = \sum\limits_{B = t,f} {\sum\limits_{E = t,f} {P(B)P(E)P(A = t|B,E)} } {\rm{  }} \\ 
  = P(B = t)P(E = t)P(A = t|B = t,E = t) + P(B = t)P(E = f)P(A = t|B = t,E = f) \\ 
  + P(B = f)P(E = t)P(A = t|B = f,E = t) + P(B = f)P(E = f)P(A = t|B = f,E = f) \\ 
  = P(B = t)P(E = t) + P(B = t)P(E = f) + P(B = f)P(E = t) \\ 
  = P(B = t)\left( {P(E = t) + P(E = f)} \right) + \left( {1 - P(B = t)} \right)P(E = t) \\ 
  = P(B = t) + P(E = t) - P(B = t)P(E = t) \\ 
 \end{array}
\]

Thus, as $P(B=t)$ and $P(E=t)$ gets smaller, $P(A=t)$ also gets smaller.  Since $P(B = t|A = t) = P(B = t)/P(A = t)$ (from (d)), $P(B=t | A=t)$ becomes much greater than $P(B=t)$. 

\item For the obtained CPT above, prove that $P(B=t | E=t, A=t) = P(B=t)$.  Which is greater between $P(B=t | E=t, A=t)$ and $P(B=t | A=t)$?   What is the meaning of this?  {\it Hint:} Note that the observation of Earthquake ($E=t$) alone is enough to explain the cause of Alarm ($A=t$).  This occurrence is called ``Explaining Away.'' 

\noindent\vspace{5mm}\textbf{Solution:}
\[
\begin{array}{l}
 P(B = t|E = t,A = t) \\ 
  = \frac{{P(B = t,E = t,A = t)}}{{P(E = t,A = t)}} \\ 
  = \frac{{P(B = t)P(E = t)P(A = t|B = t,E = t)}}{{P(E = t,A = t)}}{\rm{   ~~~~ (from ~the ~graphical ~model)}} \\ 
  = \frac{{P(B = t)P(E = t)P(A = t|B = t,E = t)}}{{P(E = t)}}{\rm{    ~~~~(since~  }}P(E = t,A = t) = P(E = t){\rm{)}} \\ 
  = P(B = t) \\ 
 \end{array}
\]

Note that in (c), we proved $P(B= t,A = t) = P(B = t)$.  In like manner, we can prove $P(E= t,A = t) = P(E = t)$.

Since $P(B=t | E=t, A=t) = P(B=t)$ and $P(B=t | A=t) \ge P(B=t)$ (from (c)),    we get

$P(B=t | A=t) \ge P(B=t) = P(B=t | E=t, A=t)$\\

Note that $P(B=t | E=t, A=t)$ denotes your belief on $B=t$ (Burglary happened) when you know both Earthquake and Alarm happened ($ E=t, A=t$).
Here the observation of Earthquake ($E=t$) alone is enough to explain the cause of Alarm ($A=t$). Therefore, since the fact that Earthquake happened can ``explain away'' the fact that Alarm happened, there is no increase in your belief on $B=t$ (Burglary happened).   Thus,  $P(B=t | E=t, A=t) = P(B=t)$.



\item We assume that $P(B=t) = 0.15$ and $P(E=t) = 0.005$.   Calculate $P(A=t), P(B=t | A=t), P(B=t | E=t, A=t), P(E=t | A=t), P(E=t | B=t, A=t)$ by hand. 

\noindent\vspace{5mm}\textbf{Solution:}

$P(A = t) = P(B = t) + P(E = t) - P(B = t)P(E = t) = 0.15 + 0.005 - 0.15 \times 0.005 = 0.15425 $\\
$P(B = t|A = t) = P(B = t)/P(A = t) = 0.15/0.15425 = 0.97245 $\\
$P(B = t|E = t,A = t) = P(B = t) = 0.15$\\
$P(E = t|A = t) = P(E = t)/P(A=t) = 0.005/0.15425 = 0.0324 $\\
$P(E = t|B=t,A = t) = P(E = t) = 0.005 $\\

\end{enumerate}
\end{document}
