\documentclass[12pt]{article}

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

\begin{document}

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

\title{\underline{Problem Set 3}}
\author{MAS 622J/1.126J: Pattern Recognition and Analysis}
\date{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 3.1-3.5.1}
%Consider a two-class recognition problem, with zero-one loss, where your training data for $\textbf{x}=[x_1\text{ }x_2]^T$ indicates that both classes are equally likely, and have reasonably Gaussian distributions as follows:
%\begin{align*}
%\omega_1:\text{~~~}\mu_1&=[2\text{ }10]^T\text{~~~}\Sigma_1=2\text{I}\\
%\omega_2:\text{~~~}\mu_2&=[20\text{ }5]^T\text{~~~}\Sigma_2=5\text{I}
%\end{align*}
%where $\text{I}$ is the identity matrix.
%\begin{enumerate}
%\item Sketch the one-sigma ellipses for $p(\textbf{x}|\omega_1)$ and $p(\textbf{x}|\omega_2)$.  Label your axes.
%\item Find a mathematical expression for the decision boundary for an unlabeled observation $x$ that minimizes that Bayes probability of error.
%\item Sketch that decision boundary on your plot from (a).  If you aren't sure of your answer in (b) then indicate this and at least sketch intuitively where you think the boundary should be.
%\item Suppose you have the same conditions above except that now both classes have covariances equal to the identity matrix, $\text{I}$.  Is the following statement true or false?
%  ``The optimal decision boundary is a line, which perfectly separates all the data.''  Explain your answer.
%\end{enumerate}

\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$.
\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$.
\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.
\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.
\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.

\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*}
\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.
\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.
\item Explain the complexity order relationship between part (b) and part (c).  Why are they the same or different?
\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)$.
\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?
\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.
\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}$.
\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?
\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$.)
\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.
\item Project the dataset onto these normalized vectors and graph the result.
\item Whiten this two dimensional distribution and graph the result.
\end{enumerate}
As usual, label your axes for both graphs.
Please include a printed copy of your program in your solution.
\end{enumerate}

%\section{DBN Inference}
%
%\begin{enumerate}
%\item a part
%\end{enumerate}

\end{document}

