\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{graphicx}

\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 September 30}
\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.]
\newline newline
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{[10 Points]} 
In many pattern classification problems we have the option to either assign a pattern to one of $\textit{c}$ classes, or reject it as unrecognizable - if the cost to reject is not too high. Let the cost of classification be defined as:
\begin{equation*}
\lambda(\omega_{i} | \omega_{j}) = 
\begin{cases} 
0 & \text{if $\omega$ $_{i}$ = $\omega$ $_{j}$,    (i.e. Correct Classification)} \\
\lambda_{r} & \text{if $\omega$ $_{i}$ = $\omega$ $_{0}$,    (i.e. Rejection)} \\
\lambda_{s} & \text{Otherwise,     (i.e. Substitution Error)}
\end{cases}
\end{equation*}
Show that for the minimum risk classification, the decision rule should associate a test vector $\textbf{\textit{x}}$ with class $\omega$ $_{i}$, if P($\omega$ $_{i} | \textbf{\textit{x}}$) $\geq$ P($\omega$ $_{j} | \textbf{\textit{x}}$) for all $\textit{j}$ and and P($\omega$ $_{i}$ | $\textbf{\textit{x}}$)  $\geq$ 1 - $\frac{\lambda_{r}}{\lambda_{s}}$, and reject otherwise.
%%%%%%%%%% SOLUTION %%%%%%%%%%

\noindent {\bf Solution}:
Average risk is choosing class $\omega_{i}$:
\begin{equation*}
R(\omega_{i} | \textbf{x}) = \sum_{j=1}^{c} \lambda(\omega_{i} | \omega_{j})P(\omega_{j} | \textbf{x}) = 0.P(\omega_{i} | \textbf{x}) + \sum_{j=1, j!=i}^{c} \lambda_{s}P(\omega_{j} | \textbf{x})
\end{equation*}
where $\lambda$($\omega_{i} | \omega_{j}$) is used to mean the cost of choosing class $\omega_{i}$ where the true class is $\omega{j}$.
\newline \newline
Hence:
\begin{equation*}
R(\omega_{i} | \textbf{x}) = \lambda_{s}(1 - P(\omega_{i} | \textbf{x}))
\end{equation*}
Associate $\textbf{x}$ with the class $\omega_{i}$ if highest posterior class probability and the average risk is less than the cost of rejection:
\begin{equation*}
\lambda_{s}(1 - P(\omega_{i} | \textbf{x})) \leq \lambda_{r}
\end{equation*}
\begin{equation*}
P(\omega_{i} | \textbf{x}) \geq 1 - \lambda_{r}/\lambda_{s}
\end{equation*}

%
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
\section{[16 points]}
In a particular binary hypothesis testing application, the conditional density for a scalar feature $\x$ given class $w_1$ is 
$$ p(\x|w_1) = k_1 \exp(-\x^2/20) $$
Given class $w_2$ the conditional density is 
$$ p(\x|w_2) = k_2 \exp(-(\x-6)^2/12) $$

\begin{enumerate}
\item Find $k_1$ and $k_2$, and plot the two densities on a single graph using Matlab.

%%%%%%%%%%%SOLUTION%%%%%%%%%%%%%
\noindent {\bf Solution}:
We solve for the parameters $k_1$ and $k_2$ by recognizing that the two equations are in the form of the normal Gaussian distribution. 

\begin{align*}
k_1e^\frac{-\x^2}{20} &= \frac{1}{\sqrt{2\pi {\sigma_1}^2}}e^\frac{-(\x-\mu_1)^2}{2\sigma_1^2} \\
\frac{-\x^2}{20} &=\frac{-(\x-\mu_1)^2}{2\sigma^2_1} \\
\mu_1 &= 0; \sigma_1^2 = 10 \\
k_1&=\frac{1}{\sqrt{20\pi }}
\end{align*}

In a similar fashion, we find that 
\begin{align*}
\mu_2 &= 6; \sigma^2_2 = 6 \\
k_2 &= \frac{1}{\sqrt{12\pi }}
\end{align*}

These distributions are plotted in Figure \ref{fig:bayes_risk}.
\begin{figure}
\center
\includegraphics[width=3in]{bayes_risk}
\caption{The pdf and decision boundaries}
\label{fig:bayes_risk}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item Assume that the prior probabilities of the two classes are equal, and that the cost for choosing correctly is zero.  If the costs for choosing incorrectly are $C_{12}=\sqrt{3}$ and $C_{21}=\sqrt{5}$, what is the expression for the conditional risk?

%%%%%%%%%%%SOLUTION%%%%%%%%%%%%%
\noindent {\bf Solution}:
The conditional risk for \emph{Two-Category Classification} is discussed in Section~2.2.1 in D.H.S.  Where we see
that the formulas for the risk associated with the action, $\alpha_i$, of classifying a feature vector, $x$, as class, $\omega_i$,
is different for each action:

\begin{align*}
R(\alpha_1|x)&=\lambda_{11}P(\omega_1|x)+\lambda_{12}P(\omega_2|x)\\
R(\alpha_2|x)&=\lambda_{21}P(\omega_1|x)+\lambda_{22}P(\omega_2|x)
\end{align*}

The prior probabilities of the two classes are equal:
\begin{align*}
P(\omega_1)=P(\omega_2)= \frac{1}{2}
\end{align*}

The assumption that the cost for choosing correctly is zero:
$$\lambda_{11}=0, \lambda_{22}=0$$

The costs for choosing incorrectly are given as $C_{12}$ and $C_{21}$:
$$\lambda_{12}=C_{12}=\sqrt{3}$$
$$\lambda_{21}=C_{21}=\sqrt{5}$$

Thus the expression for the conditional risk of $\alpha_1$ is:
\begin{align*}
R(\alpha_1|\x)&=\lambda_{11}P(\omega_1|\x)+\lambda_{12}P(\omega_2|\x)\\
R(\alpha_1|\x)&=0 P(\omega_1|\x)+ \sqrt{3} P(\omega_2|\x)\\
R(\alpha_1|\x)&= \sqrt{3} P(\omega_2|\x)
\end{align*}

And the expression for the conditional risk of $\alpha_2$:
\begin{align*}
R(\alpha_2|\x)&=\lambda_{21}P(\omega_1|\x)+\lambda_{22}P(\omega_2|\x)\\
R(\alpha_2|\x)&=\sqrt{5} P(\omega_1|\x)+0 P(\omega_2|\x)\\
R(\alpha_2|\x)&=\sqrt{5} P(\omega_1|\x)
\end{align*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item Find the decision regions which minimize the Bayes risk, and indicate them on the plot you made in part (a)

%%%%%%%%%%%SOLUTION%%%%%%%%%%%%%
\noindent {\bf Solution}:
The Bayes Risk is the integral of the conditional risk when we use the optimal decision regions, $R_1$ and $R_2$.  So, solving for the optimal decision regions is a matter of solving for the roots of the inequality:
\begin{align*}
\sqrt{3} R(\alpha_1|\x)&< \sqrt{5} R(\alpha_2|\x)\\
\sqrt{3} P(\omega_2|\x)&<\sqrt{5} P(\omega_1|\x)\\
\frac{\sqrt{3} P(\x|\omega_2)P(\omega_2)}{P(\x)}&<\frac{\sqrt{5} P(\x|\omega_1)P(\omega_1)}{P(\x)}\\
\end{align*}
Given the priors are equal this simplifies to:
\begin{align*}
\sqrt{3} P(\x|\omega_2)&< \sqrt{5} P(\x|\omega_1)
\end{align*}

Next, using the values, $k_1$ and $k_2$, from part (a), we have expressions for $p_{\x|\omega_1}$ and $p_{\x|\omega_2}$.  
\begin{align*}
\sqrt{3}\frac{1}{\sqrt{12\pi}}e^{\frac{-(\x-6)^2}{12}}&<\sqrt{5}\frac{1}{\sqrt{20\pi}}e^{\frac{-\x^2}{20}}\\
e^{\frac{-(\x-6)^2}{12}}&<e^{\frac{-\x^2}{20}}\\
\frac{-(\x-6)^2}{12}&<\frac{-\x^2}{20}\\
8 x^2 - 240 x + 720 &> 0
\end{align*}
The decision boundary is found by solving for the roots of this quadratic, $\x = 3.81$ and $\x=26.62$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item For the decision regions in part (c), what is the numerical value of the Bayes risk?

%%%%%%%%%%%SOLUTION%%%%%%%%%%%%% 
\noindent {\bf Solution}:
For $\x < 3.81$ the decision rule will choose $\omega_1$\\
For $3.81 < \x < 26.62$ the decision rule will choose $\omega_2$\\
For $26.62 < \x $ the decision rule will choose $\omega_1$

Thus the decision region $R_1$ is $\x < 3.81$ and $\x > 26.62$, and the decision region $R_2$ is $3.81 < \x < 26.62$.

\begin{align*}
Risk &= \int_{R_1} \lambda_{11}P(\omega_1|\x)+\lambda_{12}P(\omega_2|\x)\\
 	& + \int_{R_2} \lambda_{21}P(\omega_1|y)+\lambda_{22}P(\omega_2|y)\\
	&= \int_{R_1} \lambda_{12}P(y|\omega_2)P(\omega_2) + \int_{R_2} \lambda_{21}P(y|\omega_1)P(\omega_1)\\
	&= \int_{y = -\inf}^{y = 3.81} \sqrt{3} N(6,6)\frac{1}{2} + \int_{y = 26.62}^{y = \inf} \sqrt{3} N(6,6)\frac{1}{2} \\
	& + \int_{y = 3.81}^{y = 26.62} \sqrt{5}N(0,10)\frac{1}{2}\\
	&= \frac{\sqrt{3}}{2}(\frac{1}{2} - \frac{1}{2}erf((6-3.81)/\sqrt{12})) + 
\frac{\sqrt{3}}{2}(\frac{1}{2} - \frac{1}{2}erf((26.62 - 6)/\sqrt{12})) \\ 
&+ \frac{\sqrt{5}}{2}(\frac{1}{2}erf((26.62)/\sqrt{20}) - \frac{1}{2}erf((3.81)/\sqrt{20})) \\
	&= .2827
\end{align*}

\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{[16 points]} 

Let's consider a simple communication system. The transmitter sends out messages
$m = 0$ or $m = 1$, occurring with a priori probabilities $\frac{3}{4}$ and $\frac{1}{4}$ respectively. The
message is contaminated by a noise $n$, which is independent from $m$ and takes on the values -1, 0, 1 with probabilities $\frac{1}{8}$, $\frac{5}{8}$, and $\frac{2}{8}$ respectively. The received signal, or the observation, can be represented as $r = m + n$. From $r$, we wish to infer what the transmitted message $m$ was (estimated state), denoted using $\hat{m}$. $\hat{m}$ also takes values on 0 or 1. When $m = \hat{m}$, the detector correctly receives the original message, otherwise an error occurs.

\begin{figure}[h]
\center
\includegraphics[width=4in]{receiver.png}
\caption{A simple receiver}
\label{fig:receiver}
\end{figure}


\begin{enumerate}

\item Find the decision rule that achieves the maximum probability of correct decision.
Compute the probability of error for this decision rule.

\noindent {\bf Solution}:
It is equivalent to find the decision rule that achieves the minimum probability of error. The receiver decides the transmitted message is 1, i.e., $\hat{m} = 1$ if

\begin{eqnarray}
P(r | m = 1) \cdot Pr(m = 1) &\geq & P(r | m = 0) \cdot Pr(m = 0) \notag \\
P(r | m = 1) &\geq  & P(r | m = 0) \cdot 3
\label{eq:eq_prob}
\end{eqnarray}

Otherwise the receiver decides $\hat{m} = 0$. The likelihood functions for these two
cases are

\begin{eqnarray*}
P(r|m = 1) &=&
	\begin{cases} 
		\frac{1}{8} &\text{if }r = 0 \\
		\frac{5}{8} &\text{if }r = 1 \\
		\frac{2}{8} &\text{if }r = 2 \\
		0 &\text{otherwise}
	\end{cases}\\ 	
P(r|m = 0) &=&
	\begin{cases} 
		\frac{1}{8} &\text{if }r = -1 \\
		\frac{5}{8} &\text{if }r = 0 \\
		\frac{2}{8} &\text{if }r = 1 \\
		0 &\text{otherwise}
	\end{cases} 	
\end{eqnarray*}

Eq. \ref{eq:eq_prob} holds only when $r = 2$. Therefore, the decision rule can be summarized as


\begin{eqnarray*}
\hat{m} &=&
	\begin{cases} 
		1 &\text{if r = 2} \\
		0 &\text{otherwise}\\
	\end{cases}
\end{eqnarray*}

The probability of error is as follows:
\begin{eqnarray*}
Pr(e) &=& Pr( \hat{m} = 1|m = 0) \cdot Pr(m = 0) + Pr( \hat{m} = 0|m = 1)\cdot  Pr(m = 1)\\
&=& Pr(r = 1|m = 0) \cdot Pr(m = 0) + Pr(r = 0|m = 1) \cdot  Pr(m = 1)\\
&=& \frac{2}{8} \cdot  \frac{3}{4} + \frac{1}{8} \cdot  \frac{1}{4} = \frac{7}{32} = 0.2188
\end{eqnarray*}


\item Let's have the noise $n$ be a continuous random variable. $n$ is uniformly distributed
between $\frac{-3}{4}$ and $\frac{2}{4}$, and still statistically independent of $m$. First, plot the pdf
of $n$. Then, find a decision rule that achieves the minimum probability of error, and compute the probability of error.

\noindent {\bf Solution}:

The uniform distribution is plotted in Figure \ref{fig:unif_dist}.
\begin{figure}
\center
\includegraphics[width=3in]{pdf_n.pdf}
\caption{The pdf of $n$}
\label{fig:unif_dist}
\end{figure}

The decision rule is still determined by using Eq. \ref{eq:eq_prob}. The likelihood functions become
continuous, instead of discrete in (a):


\begin{eqnarray*}
P(r|m = 1) &=&
	\begin{cases} 
		\frac{4}{5} &\text{if } \frac{1}{4} < r \leq \frac{6}{4} \\
		0 &\text{otherwise} 
	\end{cases}\\ 	
P(r|m = 0) &=&
	\begin{cases} 
		\frac{4}{5} &\text{if } \frac{-3}{4} < r \leq \frac{2}{4} \\
		0 &\text{otherwise} 
	\end{cases} 	
\end{eqnarray*}

The interesting region is where the two pdf's overlap with each other, namely when $\frac{1}{4} < r \leq \frac{2}{4}$. From Eq. \ref{eq:eq_prob}, we know we should decide $\hat{m} = 0$ for this range. The decision rule can be summarized as

\begin{eqnarray*}
\hat{m} &=&
	\begin{cases} 
		0 &\text{if } \frac{-3}{4} < r \leq \frac{1}{4} \\
		0 &\text{if } \frac{1}{4} < r \leq \frac{2}{4} \\
		1 &\text{if } \frac{2}{4} < r \leq \frac{6}{4} 
	\end{cases} 	
\end{eqnarray*}

Note that at the decision boundaries, there is ambiguity on which decision we should make. Again, either decision won't change the probability of error, so it is acceptable to decide both ways.

The probability of error is

\begin{eqnarray*}
Pr(e) &=& Pr( \hat{m} = 1 | m = 0) \cdot Pr(m = 0) + Pr( \hat{m} = 0|m = 1)\cdot  Pr(m = 1)\\
&=& Pr(\frac{1}{4} < r \leq \frac{2}{4}|m = 1) \cdot Pr(m = 1)\\
&=& (\frac{2}{4} - \frac{1}{4}) \cdot \frac{4}{5} \cdot \frac{1}{4} = \frac{1}{20}
\end{eqnarray*}



\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ [16 points]}
[Note: Use Matlab for the computations, but make sure to explicitly construct every transformation required, that is either type it or write it.  Do not use Matlab if you are asked to explain/show something.]

Consider the three-dimensional normal distribution $p({\bf x}|w)$ with mean {\bf $\mu$} and covariance matrix $ \bf \Sigma$ where 

\[ {\bf \mu} = \left(\begin{array}{c}3 \\1 \\2 \end{array}\right), {\bf \Sigma} = \left(\begin{array}{ccc}1 & 0 & 0\\0 & 5 & 4\\0 & 4 & 5 \end{array}\right).\]  

Compute the matrices representing the eigenvectors and eigenvalues $\Phi$ and $\Lambda$ to answer the following questions:

%%%%%%%%%%SOLUTION%%%%%%%%%%%%
\noindent {\bf Solution}:
\[ {\bf \Lambda} = \left(\begin{array}{ccc}1 &  0 & 0\\0 &  1 & 0\\0 &  0 & 9\end{array}\right), {\bf \Phi} = \left(\begin{array}{ccc}1 & 0 & 0\\0 & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right).\]  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{enumerate}
\item Find the probability density at the point ${\bf x_0} = ($5 6 3$)^T$

%%%%%%%%%%SOLUTION%%%%%%%%%%%%
\noindent {\bf Solution}:
\begin{equation}
p(\x_0|\omega) = \frac{1}{(2\pi)^{3/2}|\Sigma|^{1/2}}e^{\frac{-(\x_0 - \mu)^T\Sigma^{-1}(\x_0-\mu)}{2}}
\end{equation}

$$ |\Sigma| = 9; \mbox{  } \Sigma^{-1} = \left(\begin{array}{ccc}1 & 0 & 0\\0 & \frac{5}{9} & \frac{-4}{9}\\0 & \frac{-4}{9} & \frac{5}{9} 
\end{array}\right)$$

The squared Mahalanobis distance from the mean to $\x_0$ is:

$$ (\x_0 - \mu)^T\Sigma^{-1}(\x_0-\mu) = $$
$$
\left[ \left( 
\begin{array}{c}5 \\6 \\3  
\end{array}\right) - \left( 
\begin{array}{c}3 \\1 \\2  
\end{array}
\right) \right]^T
\left(\begin{array}{ccc}1 & 0 & 0\\0 & \frac{5}{9} & \frac{-4}{9}\\0 & \frac{-4}{9} & \frac{5}{9} 
\end{array}\right)
\left[ \left( 
\begin{array}{c}5 \\6 \\3  
\end{array}\right) - \left( 
\begin{array}{c}3 \\1 \\2  
\end{array}
\right) \right] $$
$$ = 14$$

We plug these values in to find that the density at $\x_0$ is:
$$p(\x_0|\omega) = 1.2866e-5$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item Construct an orthonormal transformation ${\bf y}=\Phi^T{\bf x}$.  Show that for orthonormal transformations, Euclidean distances are preserved (i.e., $\|y\|^2=\|x\|^2$).

%%%%%%%%%%SOLUTION%%%%%%%%%%%%
\noindent {\bf Solution}:
\begin{align*}
 y &= \Phi^Tx\\
 &= \left(\begin{array}{ccc}1 & 0 & 0\\0 & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right)^Tx
\end{align*}

To prove that for orthonormal transformations, Euclidean distances are preserved we have to show that $||y||^2=||x||^2$.

\emph{Proof}:  
Let $y$ be a random variable such that $y=A^Tx$ where $A^T$ is an orthonormal transformation (i.e., $A^TA=I$)

\begin{align*}
 ||y||^2 &= y^Ty\\
	&= (A^Tx)^TA^Tx\\
	&= x^TAA^Tx\\
	&= x^Tx\\
	&= ||x||^2
\end{align*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item After applying the orthonormal transformation add another transformation $\Lambda^{-1/2}$ and convert the distribution to one centered on the origin with covariance matrix equal to the identity matrix. Remember that $\bf A_w = \Phi\Lambda^{-1/2}$ is a linear transformation (i.e., $ {\bf A_w}(a{\bf x}+b{\bf y}) = a{\bf A_wx}+b{\bf A_wy}$)

%%%%%%%%%%SOLUTION%%%%%%%%%%%%
\noindent {\bf Solution}:
\begin{align*}
u &= \Lambda^{-1/2}y\\
	&= \left(\begin{array}{ccc}1 &  0 & 0\\0 &  1 & 0\\0 &  0 & \frac{1}{\sqrt{9}}\end{array}\right)y
\end{align*}

Where $u$ can also be expressed as $u= \Lambda^{-1/2}\Phi^Tx$

Let $u={{\bf A_w}}^Tx$ where ${\bf A_w} = \Phi\Lambda^{-1/2}$.

Given $p(x|w) \sim N(\mu,\Sigma)$ then  $p(u|w) \sim N({{\bf A_w}}^T\mu,{{\bf A_w}}^T\Sigma{{\bf A_w}})$ 

Since $u$ is a result of a whitening transform to $x$, then the covariance matrix of $u$ is proportional to the Identity matrix $I$.  In this case, since $\Phi$ is a matrix of normalized eigenvectors of $\Sigma$ and $\Lambda$ is the eigenvalue matrix, the transformation $A^T = \Lambda^{-1/2}\Phi^T$ makes the covariance matrix equal to $I$.

Therefore, to convert the distribution to one centered on the origin with the covariance equal to the Identity matrix, it is enough to define a new variable $z$ such that $z = {{\bf A_w}}^Tx - {{\bf A_w}}^T\mu$.  In that way  $p(z|w) \sim N(0,1)$.


\item Apply the same overall transformation to $\bf \x_0$ to yield a transformed point $\bf x_w$ 

%%%%%%%%%%SOLUTION%%%%%%%%%%%%
\noindent {\bf Solution}:
\begin{align*}
 {\bf x_w} &= {\bf A_w}^T{\bf \x_0}-{\bf A_w}^T\mu \\
 		&= {\bf A_w}^T({\bf \x_0}-\mu) \\
 		&= \left( \begin{array}{ccc}1 &  0 & 0\\0 &  - \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\0 &  \frac{1}{\sqrt{18}} & \frac{1}{\sqrt{18}}\end{array}
		\right)\left( \begin{array}{c}				2\\				5\\				1\end{array} \right) \\
		&= \left( \begin{array}{c}				2\\				\frac{-4}{\sqrt{2}}\\ \frac{6}{\sqrt{18}}				
\end{array} \right)
\end{align*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item Calculate the Mahalanobis distance from $\bf x_0$  to the mean $\bf \mu$ and from $\bf x_w$  to $\bf 0$.  Are they different or are they the same?  Why?

%%%%%%%%%%SOLUTION%%%%%%%%%%%%
\noindent {\bf Solution}:
The squared Mahalanobis distance from $\bf x_0$  to the mean $\bf \mu$, we found in part (a), is .9514

The squared Mahalanobis distance from $\bf x_w$  to 0 is:

\begin{align*}
{\bf x_w}^T{\bf x_w}  
		&=  \left( \begin{array}{c}					2\\				\frac{-4}{\sqrt{2}}\\ \frac{6}{\sqrt{18}}		
			\end{array} \right)^T
			\left( \begin{array}{c}					2\\				\frac{-4}{\sqrt{2}}\\ \frac{6}{\sqrt{18}}		
			\end{array} \right) =  14
 \end{align*}

The two distances are the same, as expected under any linear transformation.

\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{[16 Points]}
Use signal detection theory as well as the notation and basic Gaussian assumptions described in the text to address the following.
\begin{enumerate}
\item Prove that ${\bf P(x>x^* | x } \in w_2)$ and ${\bf P(x>x^* | x } \in w_1)$, taken together, uniquely determine the discriminability $\bf d'$

%%%%%%%%SOLUTION%%%%%%%%%%%
\noindent {\bf Solution}:
Let ${\bf x} = x$ and  ${\bf x^*} = x^*$.  Based on the Gaussian assumption, we see that 
$ P(x>x^* | x  \in w_i) = P\left(\frac{x-\mu_i}{\sigma_i}>\frac{x^*-\mu_i}{\sigma_i} | x  \in w_i \right) \sim N(0,1)$ for $i=1,2$
Thus, we know $\left( \frac{x-\mu_2}{\sigma_2} \right)$ from the hit rate $ P(x>x^* | x \in w_2)$ and $\left( \frac{x-\mu_1}{\sigma_1} \right)$ from the false alarm rate $P(x>x^* | x \in w_1)$, and these let us calculate the discriminability.

\begin{align*}
\left|\frac{x^*-\mu_1}{\sigma_1} - \frac{x^*-\mu_2}{\sigma_2}\right| 
									&= \left|\frac{x^*-\mu_1}{\sigma} - \frac{x^*-\mu_2}{\sigma}\right| \\
									&= \left|\frac{\mu_2-\mu_1}{\sigma}\right| \\
									&= \frac{|\mu_2-\mu_1|}{\sigma} \\
									&= d'
\end{align*}

Therefore $d'$ is uniquely determined by the hit and false alarm rates.
%%%%%%%%%%%%%%%%%%%%%%%%%

\item Use error functions $erf(*)$ to express $\bf d'$ in terms of the hit and false alarm rates.  Estimate $\bf d'$ if ${\bf P(x>x^* | x } \in w_1) = .7$ and ${\bf P(x>x^* | x } \in w_2) = .5$.  Repeat for $\bf d'$ if ${\bf P(x>x^* | x } \in w_1) = .85$ and ${\bf P(x>x^* | x } \in w_2) = .15$.

%%%%%%%%SOLUTION%%%%%%%%%%%
\noindent {\bf Solution}:
There are a couple of ways in which you can proceed.  This document will detail one of them.

Let y be a random variable such that $P(y>y^*|y \in w_i) \sim N(0,1)$ for $i = 1,2$.


\begin{align*}
\frac{1}{\sqrt{2\pi}} \int_0^{y^*} e^{\frac{t^2}{2}}dt 
			&= \frac{1}{2}\left(\frac{1}{\sqrt{2\pi}} \int_{-y^*}^{y^*} e^{\frac{t^2}{2}}dt\right) \\
			& \text{let  } u= \frac{t^2}{2};  du = \frac{dt}{\sqrt{2}} \\
			& = \frac{1}{2} \left( \frac{1}{\sqrt{\pi}} \int_{\frac{-y^*}{\sqrt{2}}}^{\frac{y^*}{\sqrt{2}}} e^{-u}du \right) \\
			& = \frac{1}{2} \left( \frac{2}{\sqrt{\pi}} \int_{0}^{\frac{y^*}{\sqrt{2}}} e^{-u}du \right) \\
			& = \frac{1}{2} erf\left( \frac{y^*}{\sqrt{2}} \right) 
\end{align*}

Then, given that $ P(x>x^* | x  \in w_i) = P\left(\frac{x-\mu_i}{\sigma_i}>\frac{x^*-\mu_i}{\sigma_i} | x  \in w_i \right) \sim N(0,1)$ for $i=1,2$. 

\begin{align*}
P\left(\frac{x-\mu_i}{\sigma_i} > \frac{x^*-\mu_i}{\sigma_i} | x  \in w_i \right) 
&= 1 - P\left(\frac{x-\mu_i}{\sigma_i} < \frac{x^*-\mu_i}{\sigma_i} | x  \in w_i \right) \\
&= \begin{cases}
	1 - \left( \frac{1}{2} + \frac{1}{2}erf\left( \frac{x^*-\mu_i}{\sqrt{2}\sigma_i} \right)\right) & \text{if } \frac{x^*-\mu_i}{\sigma_i}  > 0\\
	1 - \left( \frac{1}{2} - \frac{1}{2}erf\left( \frac{\mu_i-x^*}{\sqrt{2}\sigma_i} \right)\right) & \text{if } \frac{x^*-\mu_i}{\sigma_i}  < 0 
	\end{cases}\\
&= \begin{cases}
	\frac{1}{2} - \frac{1}{2}erf\left( \frac{x^*-\mu_i}{\sqrt{2}\sigma_i} \right) & \text{if } \frac{x^*-\mu_i}{\sigma_i}  > 0\\
	\frac{1}{2} + \frac{1}{2}erf\left( \frac{\mu_i-x^*}{\sqrt{2}\sigma_i} \right) & \text{if } \frac{x^*-\mu_i}{\sigma_i}  < 0 
	\end{cases} \\
&= \begin{cases}
	\frac{1}{2} \left(1- erf\left( \frac{x^*-\mu_i}{\sqrt{2}\sigma_i} \right) \right) & \text{if } \frac{x^*-\mu_i}{\sigma_i}  > 0\\
	\frac{1}{2} \left(1 + erf\left( \frac{\mu_i-x^*}{\sqrt{2}\sigma_i} \right) \right) & \text{if } \frac{x^*-\mu_i}{\sigma_i}  < 0 
	\end{cases} \\
\end{align*}

Therefore:
\begin{align*}
\frac{x^*-\mu_i}{\sigma_i}  &= \sqrt{2}\left(erf^{-1}[1-2P(x > x^*|x \in w_i)]\right) \text{if } P(x > x^*|x \in w_i) < .5 \\
\frac{\mu_i-x^*}{\sigma_i}  &= \sqrt{2}\left(erf^{-1}[2P(x > x^*|x \in w_i) - 1]\right) \text{if } P(x > x^*|x \in w_i) > .5
\end{align*}

Then to find the values of $erf^-1()$ use a table of $erf$, a table of the cumulative normal distribution, or use Matlab $erf$ and $erfinv$ functions.

\begin{align*}
d_1^* &= \left| -\frac{\mu_1-x^*}{\sigma} - \frac{x^*-\mu_2}{\sigma} \right| \\
   & = \left| -\sqrt{2}\left(erf^{-1}[2(.7) -1]\right) - \sqrt{2}\left(erf^{-1}[2(.5) -1]\right) \right| \\
   & = \left| -\sqrt{2}\left(erf^{-1}[.4]\right) - \sqrt{2}\left(erf^{-1}[0]\right) \right| \\
   & = .??\\
\end{align*}

\begin{align*}
d_2^* &= \left| -\frac{\mu_1-x^*}{\sigma} - \frac{x^*-\mu_2}{\sigma} \right| \\
   & = \left| -\sqrt{2}\left(erf^{-1}[2(.85) -1]\right) - \sqrt{2}\left(erf^{-1}[1- 2(.15)]\right) \right| \\
   & = \left| -\sqrt{2}\left(erf^{-1}[.7]\right) - \sqrt{2}\left(erf^{-1}[.7]\right) \right| \\
   & = 0
\end{align*}
%%%%%%%%%%%%%%%%%%%%%%%%%

\item Given that the Gaussian assumption is valid, calculate the Bayes error for both the cases in (b).

%%%%%%%%SOLUTION%%%%%%%%%%%
\noindent {\bf Solution}:
According to Problem 3 
$$ \mbox{Pr[error]}= {\bf P}(w_1)\epsilon_1 + {\bf P}(w_2)\epsilon_2 $$
$$ \mbox{ where } \epsilon_1 = \int_{\chi_2} {\bf p}({\bf x}|w_1){\bf dx} 
\mbox{ and } \epsilon_2 = \int_{\chi_1} {\bf p}({\bf x}|w_2){\bf dx} 
$$

Since the regions $\chi_1$ and $\chi_2$ are defined by our decision boundary $x^*$.  We can see that 
\begin{align*}
\epsilon_1 = \int_{\chi_2} {\bf p}({\bf x}|w_1){\bf dx}  &= P(x < x^* | x \in w_1) 
					&= 1 - P(x > x^* | x \in w_1) \\
					& Similarly \\
\epsilon_2 = \int_{\chi_1} {\bf p}({\bf x}|w_2){\bf dx}  &= P(x > x^* | x \in w_2) 
\end{align*}

Therefore,
 
\begin{align*}
\text{Pr[error1]} &= (1-.7)P(w_1) +  (.5)P(w_2)  \\
\text{Pr[error2]} &= (1-.85)P(w_1) +  (.3)P(w_2) 
\end{align*}

And if the priors are equally likely, 

\begin{align*}
\text{Pr[error1]} &= .5 \\
\text{Pr[error2]} &= .15
\end{align*}
%%%%%%%%%%%%%%%%%%%%%%%%%

\item Using a trivial one-line computation or a graph determine which case has the higher $\bf d'$, and explain your logic:
$$
{\bf \mbox{\bf Case A:  }  P(x>x^* | x } \in w_1) = .75 \mbox{ and }  {\bf P(x>x^* | x } \in w_2)=.45.
$$
$$
{\bf \mbox{\bf Case B:  }  P(x>x^* | x } \in w_1) = .2 \mbox{ and }  {\bf P(x>x^* | x } \in w_2)=.9.
$$
\end{enumerate}

%%%%%%%%SOLUTION%%%%%%%%%%%
\noindent {\bf Solution}:
From part (b) we can calculate the discriminability given the hit and false alarm rates, and see that Case B has a higher discriminability.

\begin{align*}
d_1^* &= \left| -\frac{\mu_1 - x^*}{\sigma} - \frac{x^*-\mu_2}{\sigma} \right| \\
	   & = \left| -\sqrt{2}\left(erf^{-1}[2(.7) -1]\right) - \sqrt{2}\left(erf^{-1}[1 - 2(.4)]\right) \right| \\
	   & = \left| -\sqrt{2}\left(erf^{-1}[.4]\right) - \sqrt{2}\left(erf^{-1}[.2]\right) \right| \\
	   & =  .777	\\
\end{align*}

\begin{align*}
d_2^* &= \left| \frac{x^*-\mu_1}{\sigma} + \frac{\mu_2 - x^*}{\sigma} \right| \\
	   & = \left| \sqrt{2}\left(erf^{-1}[1 - 2(.2)]\right) + \sqrt{2}\left(erf^{-1}[2(.8) - 1]\right) \right| \\
	   & = \left| \sqrt{2}\left(erf^{-1}[.4]\right) + \sqrt{2}\left(erf^{-1}[.6]\right) \right| \\
	   & =  1.366	\\
\end{align*}

Key point of this problem:  The error function erf is related to the cumulative normal distribution.  Assuming that the probability of $x$ belonging to one of two classes is Gaussian, then knowing the values of the false alarm and hit rates for an arbitrary $x^*$ is enough to compute the discriminability $d'$.  Moreover, if the Gaussian assumption holds, a determination of the discriminability allows us to calculate the Bayes error rate.
%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{[16 Points]}

\begin{enumerate}
\item Show that the maximum likelihood (ML) estimation of the mean for a Gaussian is unbiased but the ML estimate of variance is biased (i.e., slightly wrong).  Show how to correct this variance estimate so that it is unbiased.   

\noindent {\bf Solution}:
Sample mean is unbiased:
\begin{align*}
E[\hat{\mu}] &= E[ \frac{1}{n} \sum_{i=1}^n x_i] \\
			&= \frac{1}{n} \sum_{i=1}^n E[ x_i] \\
			&= \frac{1}{n} \sum_{i=1}^n \mu \\
			&= \frac{1}{n} n\mu \\
			&= \mu
\end{align*}

This document will show two ways to prove that the sample variance is biased.  Proof 1:
\begin{align*}
E[ \sum_{i=1}^n (x_i - \hat{\mu})^2] &= E[ \sum_{i=1}^n (x_i)^2] - nE[\hat{\mu}^2] \\
				&= nE[(x_i)^2] - \frac{1}{n}E[(\sum_{i=1}^n x_i)^2] \\
				&= n(var(x_i) + (E[x_i])^2) - \frac{1}{n}E[(\sum_{i=1}^n x_i)^2] \\
				&= n\sigma^2 + \frac{1}{n}(nE[x_i])^2) - \frac{1}{n}E[(\sum_{i=1}^n x_i)^2] \\
				&= n\sigma^2 - \frac{1}{n}[ E[(\sum_{i=1}^n x_i)^2] - (E[\sum_{i=1}^n x_i])^2] \\
				&= n\sigma^2 - \frac{1}{n}var(\sum_{i=1}^n x_i) \\
				&= n\sigma^2 - \frac{1}{n}n\sigma^2 \\
				&= (n-1)\sigma^2 \\
\end{align*}

Proof 2:
\begin{align*}
E[ \hat{\sigma_{ML}}^2] &= E[ \frac{1}{n} \sum_{i=1}^n (x_i - \hat{\mu})^2] \\
				&= \frac{1}{n}  \sum_{i=1}^n  E[x_i^2 - 2x_i\hat{\mu} + \hat{\mu}^2] \\
				&= \frac{1}{n}  \sum_{i=1}^n  E[x_i^2]  - 2\hat{\mu}E[\sum_{i=1}^n x_i] + \sum_{i=1}^n E[\hat{\mu}^2] \\
				&= \frac{1}{n} [ n(\sigma^2 + \mu^2)  - 2nE[\hat{\mu}^2] + nE[\hat{\mu}^2] ] \\
				&= \frac{1}{n} [ n\sigma^2 + n\mu^2  - nE[\hat{\mu}^2] ]\\
				&= \frac{1}{n} [ n\sigma^2 + n\mu^2  - n (frac{\sigma^2}{n} + \mu^2) ]\\
				&= \frac{n-1}{n} \sigma^2 \\
				& Therefore \\
\text{unbiased: } \hat{\sigma}^2 &= \frac{n}{n-1} \hat{\sigma_{ML}}^2 \\
				&= \frac{1}{n-1} \sum_{i=1}^n (x_i - \hat{\mu})^2 \\
\end{align*}

\item For this part you'll write a program with Matlab to explore the biased and unbiased ML estimations of variance for a Gaussian distribution.  Find the data for this problem on the class webpage as ps2.dat.  This file contains n=5000 samples from a 1-dimensional Gaussian distribution.  

\noindent {\bf Solution}:
\begin{enumerate} 
	\item Write a program to calculate the ML estimate of the mean, and report the output.
	\item Write a program to calculate both the biased and unbiased ML estimate of the variance of this distribution.  For n=1 to 5000, plot the biased and unbiased estimates of the variance of this Gaussian.  This is as if you are being given these samples sequentially, and each time you get a new sample you are asked to re-evaluate your estimate of the variance.  Give some interpretation of your plot.


The dataset was generated from a Gaussian normal distribution $\sim N(6, 1)$.  The following Matlab code calculates the ML estimate of the mean = 6, and produces Figure \ref{fig:mlbias} indicating that the variance = 1.0.  

\begin{verbatim}
data = load('ps2.dat');
n = length(data)
%ML estimate of mean:
MLmean = sum(data) / n
MLvar = [];
unMLvar = [];
%ML estimate of variance:
for(i=2:n)
    varML = 0;
    tempMean = sum(data(1:i)) / i;   
    for (j=1:i)
        varML = varML + (data(j) - tempMean)^2;
    end
    
    MLvar(i) = varML/i;
    x = data(1:i);
    unMLvar(i) = cov(data(1:i));
end
figure
plot(1:1:n, MLvar(1:n), 'g', 1:1:n, unMLvar(1:n), 'r')
\end{verbatim}

\end{enumerate}

\begin{figure}
\center
\includegraphics[width=4in]{MLBias.jpg}
\caption{Though the two estimators have quite different estimates in the first few samples, the bias looses significance as $n$ is large, and both estimators give the true variance of the data $\sigma = 1.0$.}
\label{fig:mlbias}
\end{figure}

\end{enumerate}


\section{[10 Points]}
Suppose $\textbf{x}$ and $\textbf{y}$ are random variables.  Their joint density, depicted below, is constant in the shaded area and 0 elsewhere,

\begin{figure}[h]
\center
\includegraphics[width=4in]{P7pic.jpg}
\caption{The joint distribution of $\textbf{x}$ and $\textbf{y}$.}
\label{fig:mlbias}
\end{figure}


\begin{enumerate}
\item Let $\omega_{1}$ be the case when $\textbf{x}$ $\leq$ 0, and $\omega_{2}$ be the case when $\textbf{x}$ $>$ 0.  Determine the $\textit{a priori}$ probabilities of the two classes P($\omega_{1}$) and P($\omega_{2}$). $\textbf{y}$ is the observation. from which we infer whether $\omega_{1}$ or $\omega_{2}$ happens. Find the likelihood functions, namely, the two conditional distributions $\textit{p(y$|$$\omega_{1}$)}$ and $\textit{p(y$|$$\omega_{2}$)}$.

\noindent {\bf Solution}:

\item Find the decision rule that minimizes the probability of error, and calculate what the probability of error is.  Please note that there will be ambiguities at decision boundaries, but how you classify when $\textit{y}$ falls on the decision boundary doesn't affect the probability of error. 

\noindent {\bf Solution}:
\end{enumerate}

\end{document}
