\documentclass[12pt]{article}

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

\begin{document}

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

\title{\underline{Problem Set 3 Solutions}}
\author{MAS 622J/1.126J: Pattern Recognition and Analysis}
\date{Originally Due Monday, 16 October 2006}
\maketitle

\noindent [Note: All instructions to plot data or write a program
should be carried out using either Python accompanied by the {\tt
matplotlib} package or Matlab.  Feel free to use either or both, but
in order to maintain a reasonable level of consistency and simplicity
we ask that you do not use other software tools.]

\section{(DHS 2.6) Optimal Decision Boundaries}
Your friend has built a system to recognize into which of two categories, $\omega_1$ or $\omega_2$,
her advisor's email can be classified.  She has brilliantly identified two features such
that her 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=[8\text{ }9]^T$, $\mu_2=[0\text{ }9]^T$, $\Sigma_1=\text{I}$, and $\Sigma_2=\left[\begin{array}{rl}16&0\\0&16\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\vspace{5mm}\textbf{(Answer)}
The one sigma ellipses are circles of radii $1$ and $4$ respectively:

\noindent\includegraphics[width=5in]{ps3-1a.pdf}

The following Python program generates the graph for problem 1a:

\verbatiminput{ps3-1a.py}

The following Matlab program generates the graph for problem 1a:

\verbatiminput{ps3-1a.m}

\item Your friend finds that choosing a threshold at $x_1=4$ perfectly separates the
training examples she has; thus, she proposes that this should be the best classifier.
Show her an expression, in terms of $\textbf{x}$, which can improve her classifier with respect to minimizing the Bayes probability of error.
Assume that email from class $\omega_2$ is twice as likely as email from class $\omega_1$.

\noindent\vspace{5mm}\textbf{(Answer)}

Using discriminant functions (DHS 2.6.3) for each class, we have:
\begin{equation}
g_i(\textbf{x})=\textbf{x}'W_i\textbf{x}+\textbf{w}_i'+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'\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 twice as likely as email from class $\omega_1$, we have:
\begin{align}
P(\omega_2)&=2P(\omega_1),\text{ and}\\
P(\omega_1)+P(\omega_2)&=1.\text{ Resulting in}\\
P(\omega_1)&=\frac{1}{3},\text{ and}\\
P(\omega_2)&=\frac{2}{3}.
\end{align}
Then, plugging in our values to the discriminant equations, we have:
\begin{align}
g_1(\textbf{x}) &=            \textbf{x}'(-\frac{1}{2}\Sigma_1^{-1})                                        \textbf{x}+     (\Sigma_1^{-1}                                         \boldsymbol{\mu}_1)'                                 \textbf{x} - \frac{1}{2}\boldsymbol{\mu}_1'                          \Sigma_1^{-1}                                         \boldsymbol{\mu}_1                           - \frac{1}{2}\ln{|\Sigma_i|}                                       + \ln{P(\omega_1)}\\
                &=-\frac{1}{2}\textbf{x}'             \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}8\\9\end{array}\right]\right)' \textbf{x} - \frac{1}{2}\left[\begin{array}{c}8\\9\end{array}\right]'\left[\begin{array}{cc}1&0\\0&1\end{array}\right]^{-1}\left[\begin{array}{c}8\\9\end{array}\right] - \frac{1}{2}\ln{\left|\begin{array}{cc}1&0\\0&1\end{array}\right|} + \ln{\frac{1}{3}}\\
                &=-\frac{1}{2}\textbf{x}'\left[\begin{array}{cc}1&0\\0&1\end{array}\right]\textbf{x}+\left(\left[\begin{array}{cc}1&0\\0&1\end{array}\right]\left[\begin{array}{c}8\\9\end{array}\right]\right)' \textbf{x} -\frac{1}{2}\left[\begin{array}{c}8\\9\end{array}\right]'\left[\begin{array}{cc}1&0\\0&1\end{array}\right]\left[\begin{array}{c}8\\9\end{array}\right] - \frac{1}{2}\ln{1} + \ln{\frac{1}{3}}\\
                &=-\frac{1}{2}(x_1^2+x_2^2)+8x_1+9x_2 - \frac{145}{2} - \frac{1}{2}\ln{1} + \ln{\frac{1}{3}}\\
                &\approx-0.5(x_1^2+x_2^2)+8x_1+9x_2 - 73.60
\end{align}
and
\begin{align}
g_2(\textbf{x})&=\textbf{x}'(-\frac{1}{2}\Sigma_2^{-1})\textbf{x}+(\Sigma_2^{-1}\boldsymbol{\mu}_2)'\textbf{x} - \frac{1}{2}\boldsymbol{\mu}_2'\Sigma_2^{-1}\boldsymbol{\mu}_2 - \frac{1}{2}\ln{|\Sigma_2|} + \ln{P(\omega_2)}\\
               &=
\begin{array}{c}
-\frac{1}{2}\textbf{x}'\left[\begin{array}{cc}16&0\\0&16\end{array}\right]^{-1}\textbf{x}+\left(\left[\begin{array}{cc}16&0\\0&16\end{array}\right]^{-1}\left[\begin{array}{c}0\\9\end{array}\right]\right)'\textbf{x} - \frac{1}{2}\left[\begin{array}{c}0\\9\end{array}\right]'\left[\begin{array}{cc}16&0\\0&16\end{array}\right]^{-1}\left[\begin{array}{c}0\\9\end{array}\right] - \\
\frac{1}{2}\ln{\left|\begin{array}{cc}16&0\\0&16\end{array}\right|} + \ln{\frac{2}{3}} \end{array}\\
               &=-\frac{1}{2}\textbf{x}'\left[\begin{array}{cc}\frac{1}{16}&0\\0&\frac{1}{16}\end{array}\right]\textbf{x}+\left(\left[\begin{array}{cc}\frac{1}{16}&0\\0&\frac{1}{16}\end{array}\right]\left[\begin{array}{c}0\\9\end{array}\right]\right)'\textbf{x} - \frac{1}{2}\left[\begin{array}{c}0\\9\end{array}\right]'\left[\begin{array}{cc}\frac{1}{16}&0\\0&\frac{1}{16}\end{array}\right]\left[\begin{array}{c}0\\9\end{array}\right] - \frac{1}{2}\ln{256} + \ln{\frac{2}{3}}\\
               &=-\frac{1}{32}(x_1^2+x_2^2) + \frac{9}{16}x_2 - \frac{81}{32} - \frac{1}{2}\ln{256} + \ln{\frac{2}{3}}\\
               &\approx-0.03125(x_1^2+x_2^2) + 0.5625x_2 - 5.709
\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}
-0.5(x_1^2+x_2^2)+8x_1+9x_2 - 73.60 &> -0.03125(x_1^2+x_2^2) + 0.5625x_2 - 5.709\\
-0.4688(x_1^2+x_2^2)+8x_1+8.438x_2 &> 67.89\\
x_1^2-17.06x_1+x_2^2-18x_2 &< -144.8\\
(x_1-8.53)^2+(x_2-9)^2 &< (2.993)^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\vspace{5mm}\textbf{(Answer)}

\emph{a circle}: The decision region is a circle with mean, $\mu_d=[8.53, 9]^T$, and radius, $r=2.993$.
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.

\item She tells you new information: if she accidently treats email from class $\omega_1$ as if it
came from $\omega_2$, then this will be terrible for her career.  She estimates this error will
cost her ten times as much as the cost of misclassifying email from $\omega_2$ as $\omega_1$.
She adds that 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\vspace{5mm}\textbf{(Answer)}

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}=10$, $\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)\\
10p(\textbf{x}|\omega_1)\frac{1}{3} &> p(\textbf{x}|\omega_2)\frac{2}{3}\\
5p(\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$.

\end{enumerate}



\section{Reinforcement Learning}
This problem is an online activity.  Go to the following web page and play the reinforcement learning game:

\vspace{3mm}
\textbf{\tt{http://robotpatrol.media.mit.edu/mas622j/}}
\vspace{3mm}

\noindent So that we can keep track of who completed the activity, you will receive credit for this problem if you complete the survey at the end of the activity.
This game should probably take you about 45 minutes.

\noindent\vspace{5mm}\textbf{(Answer)}

\noindent\textbf{Training Session One}

After training the first version of the agent for around 20-30 minutes, you probably were able to get her to reach the goal at least once, but not nearly as
many times as would be needed to learn a sufficient policy for any of the random initialization states.

Estimate the size of the state space for this environment. A state is defined by the location and color of the four objects and the location of the agent.
There are four objects, two of which change color. The objects can be in four locations (table, chest, rug, agent), and the agent can be in three locations
(table chest rug).

Each of the objects can be in one of four locations; the can and the box can be two colors, and the agent can be in three locations:
\begin{align}
\text{total states}&=&(\text{box locations}) (\text{2 colors}) (\text{can locations})\\
&&(2\text{ colors}) (\text{yellow wand locations}) (\text{blue wand locations})\\
&&(\text{agent locations})\\
&=&(4)(2) (4)(2) (4) (4) (3)\\
 &=& 3072\text{ states}
\end{align}

*note that it's actually less than this since in the implementation used the agent can only hold one object at a time

This version of the agent is using a textbook Q-Learning algorithm.
This training session was meant to point out a few things to you about the basic RL approach.

\noindent\textbf{(1)} This is a very simple toy problem compared to some things you might actually want to have a machine learn to do in the real world.  But even here with 4
objects 4 locations the state space gets pretty big, and it takes quite a long time before the goal is reached for the first time.  So it's always important to
think about the state space of your problem.

\noindent\textbf{(2)} In this training session, you are providing a LOT of feedback to the agent, in a real world application the agent will likely have to deal with a much
more sparse reward signal.

\noindent\textbf{(3)} You can see first hand how random exploration, while it does get you to experience the state space, doesn't look very intelligent and doesn't work very
opportunistically.

\noindent\textbf{(4)} Generalization. You may have been struck by the states that the agent considered "new." This implementation wasn't using any generalization, so if a
policy was learned to make the smiley faces when the wand happened to be on the table, this is seen as completely different than the case when the wand is
laying on the rug. Obviously, some generalization would help considerably. In the Russell Norvig Chapter you'll find a nice discussion about generalization.

\noindent\textbf{Training Session Two}

After training the second version of the agent for around 20-30 minutes, you probably were able to get her to reach the goal several times, and it is pretty
likely that the learned policy was sufficient for the agent to be able to solve the task on its own in the test phase.

Three things changed between this version and the first training session. You were told what these three things were beforehand, but this training session was
meant to help you have an intuition about how these changes to the algorithm, presented in class, actually change the training/exploration experience.

Undo: You should have noticed that the agent tried to reverse an action that you gave negative feedback to.  Compared to the first training session, this
helps immensely in keeping the agent ``on the right track.'' However, it also means you have to be careful with your negative feedback since the agent has such
a strong response to it.  You may have noticed that you can get the agent in a loop temporarily by giving two negative rewards in a row.  In our research,
we've found that this is OK because people tend to limit their negative feedback in general and tend to give the agent significantly more positive feedback (as
if it is a social entity that needs motivation).

Guidance: Some people find this mechanism more useful than others, it seems to be a personal preference as to whether you'd rather lead the agent around or be
a watchful teacher.  But if used, the guidance mechanism significantly speeds up the learning process, by narrowing down the amount of time wasted on random
action selection.

Gaze: This is feedback for the trainer, letting the trainer know roughly how many actions the agent is choosing between.  It is most obvious in the case where
there are several things in front of the agent and the next action is to pick something up.  In this case the gazing tells you which things she considers
equally likely to be the best thing to pick up.  This gives the teacher an indication of when it would be a good time to use the guidance communication to
direct the next action selection.

\section{(DHS 2.11, 3.7) Bayes Nets and Computational Complexity}
Use the following Bayes belief net over categorical variables when answering the parts of this problem:
\begin{center}
\includegraphics[width=40mm]{ps3_bayes_graph.pdf}
\end{center}
\begin{enumerate}
\item Take advantage of the independence assumptions in the Bayes belief net in order to factor and simplify the following expression for $P(B=b)$:
\begin{equation*}
P(B=b)=\sum_{a{\in}A}\sum_{c{\in}C}\sum_{d{\in}D}\sum_{e{\in}E}\sum_{f{\in}F}P(a,b,c,d,e,f)
\end{equation*}

\noindent\vspace{5mm}\textbf{(Answer)}

\begin{align*}
  P(B=b)
  &=\sum_{a{\in}A}\sum_{c{\in}C}\sum_{d{\in}D}\sum_{e{\in}E}\sum_{f{\in}F}P(a,b,c,d,e,f)\\
  &=\sum_{a{\in}A}\sum_{c{\in}C}\sum_{d{\in}D}\sum_{e{\in}E}\sum_{f{\in}F}P(a)P(b|a)P(c|a)P(d|b)P(e|b)P(f|c,e)\\
  &=\sum_{a{\in}A}P(a)P(b|a)\sum_{c{\in}C}P(c|a)\sum_{d{\in}D}P(d|b)\sum_{e{\in}E}P(e|b)\sum_{f{\in}F}P(f|c,e)\\
  &=\sum_{a{\in}A}P(a)P(b|a)\sum_{c{\in}C}P(c|a)\sum_{d{\in}D}P(d|b)\sum_{e{\in}E}P(e|b)\sum_{f{\in}F}P(f|c,e)
\end{align*}
Note that the sum
\begin{equation}
\sum_{c{\in}C}P(c|a)\sum_{d{\in}D}P(d|b)\sum_{e{\in}E}P(e|b)\sum_{f{\in}F}P(f|c,e)=1
\end{equation}
so that we can write
\begin{equation}
P(B=b)=\sum_{a{\in}A}P(a)P(b|a)
\end{equation}

\item For this part assume that you have a computer that can perform multiplication and addition operations in one time step with memory
operations taking no time.  Assume also that the number of categories for each variable ($A$, $B$, $C$, $D$, $E$, and $F$) is $k$.
give the computational complexity ``big oh'' expression for the order of the original \emph{unsimplified} expression for $P(B=b)$
in part (a) in terms of the number of addition and multiplication operations required to compute the answer.  Also, give the numbers of additions and multiplications that are necessary.

\noindent\vspace{5mm}\textbf{(Answer)}

In the original unfactored formula for $P(B=b)$, there are $k^5-1$ additions, $O(k^5)$, while there are no multiplies, $O(1)$.  The total amount of space required to store the entire joint distribution, $P(A,B,C,D,E,F)$, naively is $k^6-1$, $O(k^6)$.

\item Using the same computer and category number assumptions in part (b),
give the ``big oh'' expression for the order of your \emph{simplified} expression for $P(B=b)$, again,
in terms of the number of addition and multiplication operations required to compute the answer.  Also, give the numbers of additions and multiplications that are necessary.

\noindent\vspace{5mm}\textbf{(Answer)}

The total number of additions, are $k-1$, $O(k)$, and the total number of multiplications is also $k-1$, $O(k)$.  The amount of space required to store the distributions is $k-1$ for $P(A)$ and $k*(k-1)$ for $P(B|A)$, or $(k+1)(k-1)$, $O(k^2)$.

\item Explain the complexity order relationship between part (b) and part (c).  Why are they the same or different?

\noindent\vspace{5mm}\textbf{(Answer)}

Part (b) shows that the time complexity (number of additions and multiplications) is significantly higher than the time complexity of part (c) especially when the number of categories, $k$, becomes large.
There is a memory complexity tradeoff in addition to the time complexity tradeoff, which results from factoring the complete joint probability table.  Both of these complexity tradeoffs are a direct result of the strong independence assumptions inherent in the Bayes Belief Net.

\item Now, in addition to the above Bayes belief net, you are told that there are only two categories for each variable, \emph{true} and \emph{false}.
You are also given these specific values for the conditional relationships:
\begin{align*}
P(A)&=1/2\\
P(B|A)&=\left\{
  \begin{array}{rl}
    2/3 &\mbox{ if $A$} \\
    1/2 &\mbox{ otherwise}
  \end{array} \right.\\
%P(C|A)&=\frac{4}{5}\\
P(C|A)&=\left\{
  \begin{array}{rl}
    1/4 &\mbox{ if $A$} \\
    2/3 &\mbox{ otherwise}
  \end{array} \right.\\
P(D|B)&=\left\{
  \begin{array}{rl}
    3/5 &\mbox{ if $B$} \\
    3/4 &\mbox{ otherwise}
  \end{array} \right.\\
P(E|B)&=\left\{
  \begin{array}{rl}
    1/3 &\mbox{ if $B$} \\
    3/7 &\mbox{ otherwise}
  \end{array} \right.\\
P(F|C,E)&=\left\{
  \begin{array}{rl}
    2/3 &\mbox{ if $C$ and $E$} \\
    5/6 &\mbox{ if $C$ and not $E$} \\
    3/4 &\mbox{ if not $C$ and $E$} \\
    1/2 &\mbox{ otherwise}
  \end{array} \right.\\
\end{align*}
Using these specific values for the conditional distributions, calculate a numerical value for $P(B)$.

\noindent\vspace{5mm}\textbf{(Answer)}

\begin{align}
P(B=b) &= \sum_{a{\in}A}P(A)P(b|A)
&= P(A)P(b|A)+P(\overline{A})P(b|\overline{A})
&=(\frac{1}{2})(\frac{2}{3})+(\frac{1}{2})(\frac{1}{2})
&=\frac{7}{12}
\end{align}

\item Using the same specific values for the conditional distributions in part (e), you are told that $F=\text{true}$.
What is the new value of $P(B)$ given this evidence?

\noindent\vspace{5mm}\textbf{(Answer)}

We will use the approach used in DHS 2.11 that avoids finding the value of the denominator in the Bayes relationship because it is more efficient in this binary state problem to calculate the numerator twice for both possible values.
We can write the conditional probabilities for $P(B|F)$ and $P(\overline{B}|F)$ in terms of an extra constant $\alpha$ in each case:
\begin{align}
P(B|F)&=\frac{P(B,F)}{P(F)}\\
      &={\alpha}P(B,F)
\end{align}
\begin{align}
P(\overline{B}|F)&=\frac{P(\overline{B},F)}{P(F)}\\
      &={\alpha}P(\overline{B},F)
\end{align}
We can then use the relationship
\begin{align}
P(B|F)+P(\overline{B}|F)&=1\\
{\alpha}P(B,F)+{\alpha}P(\overline{B},F)&=1\\
{\alpha}[P(B,F)+P(\overline{B},F)]&=1\\
{\alpha}&=\frac{1}{P(B,F)+P(\overline{B},F)}
\end{align}
to solve for alpha and then for $P(B|F)$ above.
We find $P(B,F)$:
\begin{align}
P(B,F)
&=\sum_{a{\in}A}P(a)P(B|a)\left[\sum_{c{\in}C}P(c|a)\left[\sum_{d{\in}D}P(d|B)\left[\sum_{e{\in}E}P(e|B)P(F|c,e)\right]\right]\right]\\
&=\sum_{a{\in}A}P(a)P(B|a)\left[\sum_{c{\in}C}P(c|a)\left[\sum_{d{\in}D}P(d|B)\left[P(E|B)P(F|c,E) + P(\overline{E}|B)P(F|c,\overline{E})\right]\right]\right]\\
&=\sum_{a{\in}A}P(a)P(B|a)\left[\sum_{c{\in}C}P(c|a)\left[\sum_{d{\in}D}P(d|B)\left[\frac{1}{3}P(F|c,E) + \frac{2}{3}P(F|c,\overline{E})\right]\right]\right]\\
&=\sum_{a{\in}A}P(a)P(B|a)\left[\sum_{c{\in}C}P(c|a)\left[ \begin{array}{c}\frac{3}{5}\left[\frac{1}{3}P(F|c,E)+\frac{2}{3}P(F|c,\overline{E})\right] \\ + \\
                                                           \frac{2}{5}\left[\frac{1}{3}P(F|c,E)+\frac{2}{3}P(F|c,\overline{E})\right]                   \end{array}\right]\right]\\
&=\sum_{a{\in}A}P(a)P(B|a)\left[\begin{array}{c}      P(C|a)\left[ \begin{array}{c} \frac{3}{5}\left[\frac{1}{3}P(F|C,E)+\frac{2}{3}P(F|C,\overline{E})\right] \\ + \\
                                                                                    \frac{2}{5}\left[\frac{1}{3}P(F|C,E)+\frac{2}{3}P(F|C,\overline{E})\right] \end{array} \right] \\ + \\
                                                P(\overline{C}|a)\left[ \begin{array}{c} \frac{3}{5}\left[\frac{1}{3}P(F|\overline{C},E)+\frac{2}{3}P(F|\overline{C},\overline{E})\right] \\ + \\ 
                                                                                    \frac{2}{5}\left[\frac{1}{3}P(F|\overline{C},E)+\frac{2}{3}P(F|\overline{C},\overline{E})\right] \end{array} \right] \end{array} \right]\\
&=\sum_{a{\in}A}P(a)P(B|a)\left[ \begin{array}{c}       P(C|a)\left[\frac{3}{5}\left[\frac{1}{3}\frac{2}{3}+\frac{2}{3}\frac{5}{6}\right]+\frac{2}{5}\left[\frac{1}{3}\frac{2}{3}+\frac{2}{3}\frac{5}{6}\right]\right] \\ + \\
                                                  P(\overline{C}|a)\left[\frac{3}{5}\left[\frac{1}{3}\frac{3}{4}+\frac{2}{3}\frac{1}{2}\right]+\frac{2}{5}\left[\frac{1}{3}\frac{3}{4}+\frac{2}{3}\frac{1}{2}\right]\right] \end{array}  \right]\\
&=\sum_{a{\in}A}P(a)P(B|a)\left[ \begin{array}{c}       P(C|a)\left[\frac{3}{5}\left[\frac{2}{9}+\frac{5}{9}\right]+\frac{2}{5}\left[\frac{2}{9}+\frac{5}{9}\right]\right] \\ + \\
                                                  P(\overline{C}|a)\left[\frac{3}{5}\left[\frac{1}{4}+\frac{1}{3}\right]+\frac{2}{5}\left[\frac{1}{4}+\frac{1}{3}\right]\right] \end{array} \right]\\
&=\sum_{a{\in}A}P(a)P(B|a)\left[P(C|a)\left[\frac{3}{5}\frac{7}{9}+\frac{2}{5}\frac{7}{9}\right] + P(\overline{C}|a)\left[\frac{3}{5}\frac{7}{12}+\frac{2}{5}\frac{7}{12}\right]\right]\\
&=\sum_{a{\in}A}P(a)P(B|a)\left[P(C|a)\left[\frac{7}{15}+\frac{14}{45}\right] + P(\overline{C}|a)\left[\frac{7}{20}+\frac{7}{30}\right]\right]\\
&=\sum_{a{\in}A}P(a)P(B|a)\left[P(C|a)\frac{7}{9} + P(\overline{C}|a)\frac{7}{12}\right]\\
&=P(A)P(B|A)\left[P(C|A)\frac{7}{9}+P(\overline{C}|A)\frac{7}{12}\right] + P(\overline{A})P(B|\overline{A})\left[P(C|\overline{A})\frac{7}{9}+P(\overline{C}|\overline{A})\frac{7}{12}\right]\\
&=\frac{1}{2}\frac{2}{3}\left[\frac{1}{4}\frac{7}{9}+\frac{3}{4}\frac{7}{12}\right] + \frac{1}{2}\frac{1}{2}\left[\frac{2}{3}\frac{7}{9}+\frac{1}{3}\frac{7}{12}\right]\\
&=\frac{1}{3}\left[\frac{7}{36}+\frac{7}{16}\right] + \frac{1}{4}\left[\frac{14}{27}+\frac{7}{36}\right]\\
&=\frac{1}{3}\frac{91}{144} + \frac{1}{4}\frac{77}{108}\\
&=\frac{91}{432} + \frac{77}{432}\\
&=\frac{7}{18}\approx0.38889
\end{align}

Next, we find $P(\overline{B}|F)$:
\begin{align}
P(\overline{B},F)
&=\sum_{a{\in}A}P(a)P(\overline{B}|a)\left[\sum_{c{\in}C}P(c|a)\left[\sum_{d{\in}D}P(d|\overline{B})\left[\sum_{e{\in}E}P(e|\overline{B})P(F|c,e)\right]\right]\right]\\
&=\sum_{a{\in}A}P(a)P(\overline{B}|a)\left[\sum_{c{\in}C}P(c|a)\left[\sum_{d{\in}D}P(d|\overline{B})\left[P(E|\overline{B})P(F|c,E) + P(\overline{E}|\overline{B})P(F|c,\overline{E})\right]\right]\right]\\
&=\sum_{a{\in}A}P(a)P(\overline{B}|a)\left[\sum_{c{\in}C}P(c|a)\left[\sum_{d{\in}D}P(d|\overline{B})\left[\frac{3}{7}P(F|c,E) + \frac{4}{7}P(F|c,\overline{E})\right]\right]\right]\\
&=\sum_{a{\in}A}P(a)P(\overline{B}|a)\left[\sum_{c{\in}C}P(c|a)\left[ \begin{array}{c}\frac{3}{4}\left[\frac{3}{7}P(F|c,E)+\frac{4}{7}P(F|c,\overline{E})\right] \\ + \\
                                                           \frac{1}{4}\left[\frac{3}{7}P(F|c,E)+\frac{4}{7}P(F|c,\overline{E})\right]                   \end{array}\right]\right]\\
&=\sum_{a{\in}A}P(a)P(\overline{B}|a)\left[\begin{array}{c}      P(C|a)\left[ \begin{array}{c} \frac{3}{4}\left[\frac{3}{7}P(F|C,E)           +\frac{4}{7}P(F|C,\overline{E})\right] \\ + \\
                                                                                               \frac{1}{4}\left[\frac{3}{7}P(F|C,E)           +\frac{4}{7}P(F|C,\overline{E})\right] \end{array} \right] \\ + \\
                                                      P(\overline{C}|a)\left[ \begin{array}{c} \frac{3}{4}\left[\frac{3}{7}P(F|\overline{C},E)+\frac{4}{7}P(F|\overline{C},\overline{E})\right] \\ + \\ 
                                                                                               \frac{1}{4}\left[\frac{3}{7}P(F|\overline{C},E)+\frac{4}{7}P(F|\overline{C},\overline{E})\right] \end{array} \right] \end{array} \right]\\
&=\sum_{a{\in}A}P(a)P(\overline{B}|a)\left[ \begin{array}{c}     P(C|a)\left[\frac{3}{4}\left[\frac{3}{7}\frac{2}{3}+\frac{4}{7}\frac{5}{6}\right]+\frac{1}{4}\left[\frac{3}{7}\frac{2}{3}+\frac{4}{7}\frac{5}{6}\right]\right] \\ + \\
                                                      P(\overline{C}|a)\left[\frac{3}{4}\left[\frac{3}{7}\frac{3}{4}+\frac{4}{7}\frac{1}{2}\right]+\frac{1}{4}\left[\frac{3}{7}\frac{3}{4}+\frac{4}{7}\frac{1}{2}\right]\right] \end{array}  \right]\\
&=\sum_{a{\in}A}P(a)P(\overline{B}|a)\left[ \begin{array}{c}     P(C|a)\left[\frac{3}{4}\left[\frac{2}{7}  +           \frac{10}{21}         \right]+\frac{1}{4}\left[\frac{2}{7}             +\frac{10}{21}         \right]\right] \\ + \\
                                                      P(\overline{C}|a)\left[\frac{3}{4}\left[\frac{9}{28} +           \frac{2}{7}           \right]+\frac{1}{4}\left[\frac{9}{28}            +\frac{2}{7}           \right]\right] \end{array} \right]\\
&=\sum_{a{\in}A}P(a)P(\overline{B}|a)\left[                      P(C|a)\left[\frac{3}{4}      \frac{2}{7}  +\frac{3}{4}\frac{10}{21}                +\frac{1}{4}      \frac{2}{7}  +\frac{1}{4}\frac{10}{21}                \right] +
                                                      P(\overline{C}|a)\left[\frac{3}{4}      \frac{9}{28} +\frac{3}{4}\frac{2}{7}                  +\frac{1}{4}      \frac{9}{28} +\frac{1}{4}\frac{2}{7}                  \right]\right]\\
&=\sum_{a{\in}A}P(a)P(\overline{B}|a)\left[                      P(C|a)\left[\frac{3}{13}                  +\frac{5}{14}                            +\frac{2}{28}                  +\frac{5}{42}                            \right] +
                                                      P(\overline{C}|a)\left[\frac{27}{112}                +\frac{3}{14}                            +\frac{9}{112}                 +\frac{2}{28}\right]\right]\\
&=\sum_{a{\in}A}P(a)P(\overline{B}|a)\left[P(C|a)\frac{425}{526} + P(\overline{C}|a)\frac{17}{28}\right]\\
&=P(A)       P(\overline{B}|A)\left[P(C|A)     \frac{425}{526}+P(\overline{C}|A)\frac{17}{28}\right] + P(\overline{A})P(\overline{B}|\overline{A})\left[P(C|\overline{A})\frac{425}{526}+P(\overline{C}|\overline{A})\frac{17}{28}\right]\\
&=\frac{1}{2}\frac{1}{3}      \left[\frac{1}{4}\frac{425}{526}+\frac{3}{4}      \frac{17}{28}\right] + \frac{1}{2}    \frac{1}{2}                 \left[\frac{2}{3}      \frac{425}{526}+\frac{1}{3}                 \frac{17}{28}\right]\\
&=\frac{1}{6}                 \left[\frac{425}{2104}          +\frac{51}{112}                \right] + \frac{1}{4}                                \left[\frac{425}{789}                 +\frac{17}{84}                            \right]\\
&=\frac{1}{6}\frac{19363}{29456} + \frac{1}{4}\frac{5457}{7364}\\
&=\frac{19363}{176736} + \frac{5457}{29456}\\
&=\frac{52105}{176736}\approx0.29482
\end{align}

So, now we can use $P(B,F)$ and $P(\overline{B},F)$ to find $\alpha$:
\begin{align}
{\alpha}&=\frac{1}{P(B,F)+P(\overline{B},F)}\\
{\alpha}&\approx\frac{1}{0.38889+0.29482}\\
{\alpha}&\approx1.4626
\end{align}
And using $\alpha$ we can now solve for $P(B|F)$:
\begin{align}
P(B|F)&={\alpha}P(B,F)\\
      &\approx(1.4626)(0.38889)\\
      &\approx0.56879
\end{align}

\end{enumerate}

\section{(DHS 3.8) PCA Dimensionality Reduction}
Standard Principle Component Analysis (PCA) transforms the data using only the eigenvectors with the largest associated eigenvalues, thus reducing dimensionality.
\begin{enumerate}
\item Standard PCA is not generally considered optimal for pattern classification.  Why not?
What is the typical optimality criterion that is violated?  Draw a picture or
give an example to argue where PCA fails.

\noindent\vspace{5mm}\textbf{(Answer)}

Standard PCA optimally reduces the dimensionality of a dataset with respect to the mean squared error (MSE) of the reconstructed datapoints.
PCA is considered an optimal way to represent the data with respect to the MSE.
PCA does not emphasize any differences between classes of datapoints, so it does not attempt to be optimal for emphasizing the components of the dataset that would help in classification problems.
PCA violates a discriminability criterion by often ignoring those components of the data that may help to optimally discriminate classes.

\item Let's explore a variation on standard PCA.  Let $R_1$ and $R_2$ be correlation matrices for two classes of
observation vectors.  Thus $R_i=E[\textbf{x}\textbf{x}^T]$ for $\textbf{x}{\in}\omega_i$.  Now define
$R=R_1+R_2$, and let $S$ be the linear transformation that whitens $R$.  Define $R'_1=S^TR_1S$ and $R'_2=S^TR_2S$.
Let $\textbf{e}$ be an eigenvector of $R'_1$ and let $\lambda$ be the associated eigenvalue.
\begin{enumerate}[i]
\item Write an expression for $S^TRS$ in terms of $R'_1$, $R'_2$, and the identity matrix $\text{I}$.

\noindent\vspace{5mm}\textbf{(Answer)}

\begin{equation}
S^TRS=S^T(R_1+R_2)S=S^TR_1S+S^TR_2S=R'_1+R'_2=I
\end{equation}

\item Show that if $\textbf{e}$ is an eigenvector of $R'_1$ then it is also an eigenvector of $R'_2$.  Write
an expression for $R'_2\textbf{e}$ in terms of $\lambda$, $\text{I}$, and $\textbf{e}$.  If $\lambda$ is the associated eigenvalue
for $R'_1$ then what is the associated eigenvalue for $R'_2$?  As the eigenvalues are ordered from largest to smallest for one class,
what happens to the eigenvalues for the other class?

\noindent\vspace{5mm}\textbf{(Answer)}

\begin{align}
(R'_2-{\lambda}I)\textbf{e}&=0\\
[(I-R'_1)-{\lambda}I]\textbf{e}&=0\\
[-R'_1+(1-{\lambda})I]\textbf{e}&=0\\
[R'_1-(1-{\lambda})I]\textbf{e}&=0
\end{align}

So, $\textbf{e}$ is an eigenvector of both $R'_2$ and $R'_1$ with eigenvalues being $\lambda$ and $1-\lambda$ respectively.
This means that the most significant principle components of one class of data are the least significant principle components of another class of data.

\item Suppose that data $\textbf{x}$ is linearly transformed so that $\textbf{y}=Q^TS^T\textbf{x}$, where each column
of $Q$ can be chosen to be an eigenvector of $R'_1$ (and thus, via what you have shown above, also an eigenvector of $R'_2$).
Which eigenvectors are likely to be best to use for representing data from both $\omega_1$ and $\omega_2$?
(Hint: Consider the relationship between the eigenvalues of $R'_1$ and those of $R'_2$.)

\noindent\vspace{5mm}\textbf{(Answer)}

The eigenvectors that are principle components relative to $R'_1$ will be the least principle components relative to $R'_2$ and vice versa.
If we want to select $d$ components to represent each category of data, then we would choose the top $d$ principle components from one category and the top $d$ principle components from the other category.
One category's set of principle eigenvectors will be the least principle eigenvectors relative to the other category, so as long as $d<=n/2$ there will not be duplicate eigenvectors chosen using this method.

\end{enumerate}
\item On the course website there is a dataset that contains 1000 five-dimensional points that are samples from a five-dimensional
probability distribution.
\begin{enumerate}[i]
\item Use a program to calculate the first two principle components (PCs) of this dataset.

\noindent\vspace{5mm}\textbf{(Answer)}

The first two principle component vectors are:
\begin{equation}
v_p=\left[\begin{array}{rrrrr}    0.1339 &  -0.8928 &  -0.1051 &   0.3399 &   0.2417 \\
                                  0.7111 &   0.2249 &   0.5048 &   0.1877 &   0.3921 \end{array}\right]^T
\end{equation}

\item Project the dataset onto these normalized vectors and graph the result.

\noindent\vspace{5mm}\textbf{(Answer)}

\includegraphics[width=5in]{ps3-4cii.pdf}

\item Whiten this two dimensional distribution and graph the result.

\noindent\vspace{5mm}\textbf{(Answer)}

\includegraphics[width=5in]{ps3-4ciii.pdf}

\end{enumerate}
As usual, label your axes for both graphs.
Please include a printed copy of your program in your solution.
\end{enumerate}

\noindent\vspace{5mm}\textbf{(Answer)}

The following Python program generates the eigenvectors and graphs for problem 4:

\verbatiminput{ps3-4c.py}

The following Matlab program generates the eigenvectors and graphs for problem 4:

\verbatiminput{ps3-4c.m}

\end{document}

