\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{(DHS 2.6) Optimal Decision Boundaries}
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\vspace{5mm}\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}
\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\vspace{5mm}\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\vspace{5mm}\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}
\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\vspace{5mm}\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}
\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{Dimensionality Reduction}

\end{document}
