\documentclass[12pt]{article}

\usepackage{array}
\usepackage{graphicx}
\textheight=9.3in
\topmargin=-.5in
\textwidth=7in
\oddsidemargin=-.3in

\def\a{\mathbf{a}}
\def\w{\mathbf{w}}
\def\x{\mathbf{x}}
\def\y{\mathbf{y}}
\def\z{\mathbf{z}}
\def\U{\mathbf{U}}

\begin{document}
\title{CSC2515 --- Assignment \#3 Answers}
\author{Behdad Esfahbod\\993505827}
\maketitle

\section{Mixture of Base Rates (7\%)}
\begin{itemize}
\item%1
The complete (joint) log likelihood:
\begin{eqnarray*}
\log p(\x,k) &=&
\log p(c = k) + \log p(\x|c = k)
\\&=&
\log\alpha_k +\sum_i\log p(x_i|c=k)
\\&=&
\log\alpha_k+\sum_i\log\prod_{j\in V_i} a_{ijk}^{[x_i=j]}
\\&=&
\log\alpha_k+\sum_i\sum_{j\in V_i} [x_i=j]\log a_{ijk}
\end{eqnarray*}

\item%2
The E-step: The posterior probability:
\begin{eqnarray*}
p(k|\x^n) &=&
\frac{p(\x^n|k)p(k)}{p(\x^n)}
\\&=&
\frac
{\alpha_k\prod_i\prod_{j\in V_i}a_{ijk}^{[x_i^n=j]}}
{\sum_k\alpha_k\prod_i\prod_{j\in V_i}a_{ijk}^{[x_i^n=j]}}
\end{eqnarray*}

\item%3
The expected complete log likelihood:
\begin{eqnarray*}
\ell &=& \log p(\{\x\}) = \sum_n\sum_k p(k|\x^n)\log p(\x^n,k)
\\&=&
\sum_n\sum_k p(k|\x^n)
\left\{
\log\alpha_k+\sum_i\sum_{j\in V_i} [x_i^n=j]\log a_{ijk}
\right\}
\end{eqnarray*}

\item%4
The M-step: $a_{ijk}$'s:
\begin{eqnarray*}
c_{ik}(\a) &=& 1-\sum_j a_{ijk} \\
\\
L(\a,\lambda) &=& \ell + \sum_i\sum_k\lambda_{ik} c(\a) \\
\\
\frac{\partial L}{\partial a_{ijk}}&=&
\sum_n p(k|\x^n) [x_i^n=j] \frac1{a_{ijk}} - \lambda_{ik} = 
\frac1{a_{ijk}}\sum_n p(k|\x^n) [x_i^n=j] - \lambda_{ik} = 0 \\
\\
a_{ijk} &=&
\frac1{\lambda_{ik}}\sum_n[x_i^n=j]p(k|\x^n)
\\\\
c_{ik}(\a) &=& 1-\sum_j a_{ijk} =
1-\frac1{\lambda_{ik}}\sum_j\sum_n[x_i^n=j]p(k|\x^n)=
1-\frac1{\lambda_{ik}}\sum_n p(k|\x^n)=0 \\
\\
\lambda_{ik} &=& \sum_n p(k|\x^n) =0 \\
\\
a_{ijk} &=&
\frac
{\sum_n[x_i^n=j]p(k|\x^n)}
{\sum_n p(k|\x^n)}
\end{eqnarray*}

\item%5
The M-step: $\alpha_k$'s:
\begin{eqnarray*}
c(\alpha) &=& 1-\sum_k \alpha_k \\
\\
L(\alpha,\lambda) &=& \ell + \lambda c(\alpha) \\
\\
\frac{\partial L}{\partial \alpha_k}&=&
\sum_n p(k|\x^n) \frac1{\alpha_k} - \lambda = 
\frac1{\alpha_k}\sum_n p(k|\x^n) - \lambda = 0 \\
\\
\alpha_k &=&
\frac1{\lambda}\sum_np(k|\x^n)
\\\\
c(\alpha) &=& 1-\sum_k \alpha_k =
1-\frac1{\lambda}\sum_k\sum_n p(k|\x^n)=
1-\frac1{\lambda}\sum_n\sum_k p(k|\x^n)\\
  &=&
1-\frac1{\lambda}\sum_n 1=
1-\frac n{\lambda}=0 \\
\\
\lambda &=& n \\
\\
\alpha_k &=&
\frac1n\sum_np(k|\x^n)
\end{eqnarray*}

\item%6
The given $q_k$ is simply $\log(p(x|k)p(k))$.  So, starting with $e^{q_k}$,
all we need is to divide it by $p(x)$ which is the sum over $k$
of $e^{q_k}$ itself.  Putting together:
$$p(k|x)=\frac{e^{q_k}}{\sum_k e^{q_k}}$$
so, taking $\log$ and using \textsf{logsum} instead of summation,
the log of the answer is:
$$\log p(k|x) = q_k - \mathrm{logsum}_k(q_k)$$
which is stable.  Now we can achieve the non-log'ed answer by 
exponentiating this, getting:
$$p(k|x) = \exp\left\{q_k - \mathrm{logsum}_k(q_k)\right\}.$$

\item%7
``Mixture of Gaussians with diagonal covariances''
\end{itemize}


\section{EM Algorithm for Factor Analysis}
\subsection*{Six Faces}
\begin{center}
\noindent
\begin{tabular}{p{.25\textwidth}@{\hspace{.120\textwidth}}
  p{.25\textwidth}@{\hspace{.120\textwidth}}p{.25\textwidth}}
$\mu$\newline
black=57\newline
white=224
&
init $\Lambda_1$\newline
black=-3\newline
white=3
&
init $\Lambda_2$\newline
black=-3\newline
white=3
\end{tabular}
\includegraphics[width=\textwidth]{code/faces1.pdf}
\begin{tabular}{p{.25\textwidth}@{\hspace{.120\textwidth}}
  p{.25\textwidth}@{\hspace{.120\textwidth}}p{.25\textwidth}}
$\mathrm{diag}(\Psi)$\newline
black=11\newline
white=3906
&
$\Lambda_1$\newline
black=-26\newline
white=16
&
$\Lambda_2$\newline
black=-26\newline
white=21
\end{tabular}
\end{center}
\medskip\par\noindent
All black and white values have been rounded to nearest integer.
Grayscales are linear between the black and white values. $\Psi$ has
been initialized to a diagonal matrix, with each entry uniformly chosen
between zero and twice the same entry in the covariance matrix of the
data.  $\Lambda$'s have been initialized using standard normal distribution.

\newpage
\subsection*{EM Average Training Log Likelihood Trajectory}
\noindent
\includegraphics[width=\textwidth]{code/trajectory.pdf}
For the convergence condition, I used
(\texttt{newlik}-\texttt{oldlik})/\texttt{newlik}$<$2e-5 and ran
EM 10 times and got the best solution.  Then continued the EM algorithm
on this best solution until the tighter convergence of
(\texttt{newlik}-\texttt{oldlik})/\texttt{newlik}$<$2e-6 was achieved.
The step shape above shows that it took some time until the best rotation
of the hidden parameters was found.  The computed value of the mean
log likelihood ignores some constant additive terms, so not to be
compared to the log likelihood values that follow.

\newpage
\subsection*{Training and Test Sets Log Likelihood}
\begin{center}
\noindent
\includegraphics[height=.45\textheight]{code/liktrain.pdf}\\
\includegraphics[height=.45\textheight]{code/liktest.pdf}
\end{center}
\noindent
There are 200 bins per histogram.  Means, an average of ten
data points per bin.

\newpage
\subsection*{Hidden Variables}
\noindent
\includegraphics[width=\textwidth]{code/z.pdf}\\
2D scatter plot of $z_1$ and $z_2$.  Apparently data is mostly
divided into two clusters, mainly identified by the $z_1$ value.

\subsection*{And Their Interpretations}
By \emph{animating} the images in a sequence, sorted one on $z_1$
and another time on $z_2$, it can be seen that:
\begin{itemize}
\item $z_1$ models whether the face is smiling or not.  The
negative values mostly correspond to non-smiling faces, while
positive values mostly correspond to smiling faces.

\item $z_2$ models the direction that face is facing to.  The
negative values mostly correspond to faces facing to the right of
the page, while positive values mostly correspond to faces facing to
the left.
\end{itemize}
These observations can be verified by looking at the images in 
the next page.

\newpage
\subsection*{Six More Faces}
\noindent
\includegraphics[width=\textwidth]{code/faces2.pdf}\\
The three images in a vertical row, from bottom to top,
correspond to the images with smallest, median, and largest
posterior values on $z_2$.  The three remaining images, from left to right,
correspond to the images with smallest, median, and largest
posterior values on $z_1$.

\subsection*{Classification}
By using the minimum training log likelihood as the threshold, I got
-4494 as the threshold and 29.1\% test error.  Since this in not the
best possible choice of threshold, because it is quite unstable and
depends on the \emph{worst} training case, I used another approach to
build a better classifier.

First I divided training points into 196 bins based on their log likelihood
(200 was again chosen such that average number of data points per bin
 is ten), then I found the bin with least log likelihood center that
had a number of data points in it that was not less than 5\% of the 
maximum number of data points in all bins.  The the edge of this bin
and the previous bin was taken as the threshold.  This way, threshold
was set to -2823, training error was 3.6\% and test error of 3.97\%.

\end{document}
