\documentclass{article}
\usepackage{array}
\usepackage{graphicx}
\textheight=1.1\textheight

\begin{document}
\title{CSC2515 --- Assignment \#1 Answers}
\author{Behdad Esfahbod\footnote{Not registered in the course yet.  Already
talked to Sam and will
do late-registration after administration problem is resolved.}
\\993505827}
\maketitle

\section{Training/Testing Error Curves (1.5\%)}
The crossing pair of lines are exactly the ones as in graphs below.  In other
words, training set error crosses Bayes error, but test set error does not.
\begin{itemize}
\item Fixed training set size: $$\mbox{\includegraphics{a111.mps}}$$
\item Fixed model complexity: $$\mbox{\includegraphics{a112.mps}}$$
\end{itemize}


\break
\section{Learning Random Boolean Functions (2.5\%)}
\begin{itemize}
\item\textbf{$\mathbf a$:}
\def\N{{\cal N}}
Let $\N$ be the multiset of training cases.
$$
a = E(\sum_{x\in\N}A_x)
  = \sum_{x\in\N}E(A_x)
$$
where $A_x$ is a random variable that is zero if $x\not\in\N$ and 1
otherwise.
$$
A_x = 1-p(x\not\in\N)
    = 1-\prod_{x_0\in\N}p(x\not=x_0)
    = 1-(\frac{2^k-1}{2^k})^N
$$
Putting together:
$$
a = \sum_{x\in\N}E(A_x)
  = 2^k\left(1-(\frac{2^k-1}{2^k})^N\right)
  = \frac{2^k-(2^k-1)^N}{2^{k(N-1)}}
$$


\item\textbf{$\mathbf b$:}
\def\M{{\cal M}}
Let $\M$ be the multiset of test cases.
$$
b = E(\sum_{x\in\M}B_x)
  = \sum_{x\in\M}E(B_x)
$$
where $B_x$ is a random variable that is zero if $x\not\in\N$ and 1
otherwise.
$$
B_x = p(x\in\N)
    = \frac{a}{2^k}
$$
Putting together:
$$
b = \sum_{x\in\M}E(B_x)
  = \frac{Ma}{2^k}
$$


\item\textbf{Lowest error rate:}
$$
   \frac{0*b+\frac12*(M-b)}{M}
 = \frac{M-b}{2M}
$$

\textbf{Algorithm:} If test case has been in training cases, return the
output to one such training case; return 0 otherwise.

\textbf{Argument:} For seen cases, error is zero.  For the rest, they are
independently and uniformly distributed among classes, so no difference
what to decide.


\item\textbf{Generalization:}
Yes.  Because the error rate
$$
\frac{M-b}{2M} = 1-\frac{a}{2^k}
$$
is independent of the test set.
\end{itemize}


\break
\section{Class-Conditional Gaussians (3\%)}
\begin{itemize}
\def\x{\mathbf{x}}
\item
\begin{eqnarray*}
p(y=k|\x) 
& = & \frac{p(\x|y=k)p(y=k)}{p(\x)}
  =   \frac{p(\x|y=k)\alpha_k}{\sum_{k=1}^{K}p(\x|y=k)\alpha_k}
  \\
& = & \frac
{\alpha_k\exp\left\{-\sum_{i=1}^D\frac1{2\sigma_i^2}(x_i-\mu_{ki})^2\right\}}%
{\sum_{k=1}^K\alpha_k\exp\left\{-\sum_{i=1}^D\frac1{2\sigma_i^2}(x_i-\mu_{ki})^2\right\}\alpha_k}%
\end{eqnarray*}


\item
\begin{eqnarray*}
\ell(\theta;D)
& = & \log p(y^1,x^1,y^2,x^2,\dots,y^M,x^M|\theta) \\
& = & \log \prod_{j=1}^M p(y^j,x^j|\theta)
  =   \sum_{j=1}^M \log p(y^j,x^j|\theta)
  =   \sum_{j=1}^M \left(\log p(x^j|y^j,\theta)+\log p(y^j)\right) \\
& = & \sum_{j=1}^M\left[
      -\frac12\sum_{i=1}^D\log(2\pi\sigma_i^2)
      -\sum_{i=1}^D\frac1{2\sigma_i^2}(x^j_i-\mu_{y_ji})^2
      +\log\alpha_{y^j}
      \right]
\end{eqnarray*}


\item
\begin{eqnarray*}
\frac{\partial\ell(\cdot)}{\partial\mu_{ki}}
& = & \frac1{\sigma_i^2}\sum_{j:\thinspace y^j=k}(\mu_k-x^j_i)
\\
\frac{\partial\ell(\cdot)}{\partial\log\sigma_i^2}
& = & \sum_{j=1}^M
      \frac{\partial}{\partial\log\sigma_i^2}
        \left[-\frac12\log\sigma_i^2
	  -\frac12e^{-\log\sigma_i^2}(x^j_i-\mu_{y_ji})^2
        \right]
\\
& = & -\frac M2
      +\frac1{2\sigma_i^2}
      \sum_{j=1}^M (x^j_i-\mu_{y_ji})^2
\\
\frac{\partial\ell(\cdot)}{\partial\alpha_k}
& = & \sum_{j:\thinspace y^j=k}\frac1{\alpha_k}
\end{eqnarray*}


\item
\begin{eqnarray*}
\sum_{j:\thinspace y^j=k}(\mu_k-x^j_i)=0
& \Rightarrow &
\mu_k = \frac{\sum_{j:\thinspace y^j=k}x_i^j}{\sum_{j:\thinspace y^j=k}1}
\\
-\frac M2 +\frac1{2\sigma_i^2} \sum_{j=1}^M (x^j_i-\mu_{y_ji})^2 = 0
& \Rightarrow &
\sigma_i^2 = \frac1M\sum_{j=1}^M(x_i^j-\mu_{y^ji})^2
\end{eqnarray*}

Using Lagrange Multipliers for class priors to sum them up to one:
\begin{eqnarray*}
L(\mathbf{\alpha},\lambda)=\ell(\cdot)+\lambda c(\mathbf{\alpha})\\
c(\mathbf{\alpha}) = 1-\sum_{k=1}^K\alpha_k
\end{eqnarray*}

Means:
\begin{eqnarray*}
\frac{\partial L(\cdot)}{\partial \mathbf{\alpha}}=0
& \Rightarrow &
\lambda + \sum_{j:\thinspace y^j=k}\frac1{\alpha_k} = 0
\\
\frac{\partial L(\cdot)}{\partial \lambda}=0
& \Rightarrow &
1-\sum_{k=1}^K\alpha_k = 0
\end{eqnarray*}

Solving for $\lambda$ first and $\sigma_k$ next gives:
\begin{eqnarray*}
\lambda & = & M\\
\alpha_k & = & \frac{\sum_{j:\thinspace y^j=k}1}{M}
\end{eqnarray*}
and observe that fortunately $\alpha_k$'s are all positive and less than one.
\end{itemize}



\break
\section{Handwritten Digit Classification (11\%)}
The images are in row-major, top to bottom, left to right.

\subsection{$K$-NN Classifier}
I broke ties by getting the first item, i.e.~the one with smallest
index.  This way $k=1$ turned out to be the best $k$ as can be seen
in the graph below:
$$\mbox{\includegraphics[width=\textwidth]{knn_best_k.pdf}}$$

\break
\subsection{Conditional Gaussian Classifier Training}
For the means, I took black for zero, and white for maximum value
over all means, using linear grayscale in between.  For log of
covariances, mapped black to the minimum over all values of the diagonals
and white to the maximum of them, again using linear grayscale
in between.  The image of covariances is a lot less \emph{blurred}
if I draw covariance diagonals themselves instead of the log of them and
map colors linearly.
$$\mbox{\includegraphics[width=\textwidth]{gaussian_plot.pdf}}$$


\subsection{Na\"ive Bayes Classifier Training}
Black represents the minimum over all values of the logs
and white represents the maximum of them, using linear grayscale
in between.
$$\mbox{\includegraphics[width=\textwidth]{naive_plot.pdf}}$$


\break
\subsection{Performance Evaluation}
\begin{table*}[h]
\begin{center}
\begin{tabular}{r|c|c}
& Gaussian-conditional & Na\"ive Bayes \\
\hline
training set & -63.7881 & -12.7559 \\
test set     & -62.3942 & -12.7017 \\
\end{tabular}
\end{center}
\caption{Average conditional log likelihood}
\end{table*}

\def\o{\phantom0}
\begin{table*}[h]
\begin{center}
\begin{tabular}{r|c|c|c}
& $K$-NN & Gaussian-conditional & Na\"ive Bayes \\
\hline
1 &\o1 (0.25\%) &\o0 (0.00\%) & 162 (23.14\%) \\
2 & 11 (2.75\%) &\o5 (1.25\%) & 174 (24.86\%) \\
3 & 21 (5.25\%) & 13 (3.25\%) & 141 (20.14\%) \\
4 & 14 (3.50\%) & 11 (2.75\%) & 147 (21.00\%) \\
5 & 19 (4.75\%) & 17 (4.25\%) & 178 (25.43\%) \\
6 &\o7 (1.75\%) &\o9 (2.25\%) &\o93 (13.29\%) \\
7 & 13 (3.25\%) & 14 (3.50\%) & 157 (22.43\%) \\
8 & 26 (6.50\%) & 21 (5.25\%) & 225 (32.14\%) \\
9 & 11 (2.75\%) & 15 (3.75\%) & 227 (32.43\%) \\
0 &\o2 (0.50\%) &\o4 (1.00\%) &\o77 (11.00\%) \\
\hline
total & 125 (3.125\%)  & 109 (2.725\%) & 1581 (22.59\%) \\
\end{tabular}
\end{center}
\caption{Error cases on test sets}
\end{table*}

\begin{table*}[h]
\begin{center}
\begin{tabular}{r|c|c|c}
& $K$-NN & Gaussian-conditional & Na\"ive Bayes \\
\hline
1 &\o1 (0.14\%) &\o3 (0.43\%) &\o87 (21.75\%) \\
2 & 25 (3.57\%) & 12 (1.71\%) & 106 (26.50\%) \\
3 & 26 (3.71\%) & 11 (1.57\%) &\o91 (22.75\%) \\
4 & 31 (4.43\%) & 19 (2.71\%) &\o85 (21.25\%) \\
5 & 22 (3.14\%) & 13 (1.86\%) & 110 (27.50\%) \\
6 &\o9 (1.29\%) &\o5 (0.71\%) &\o60 (15.00\%) \\
7 & 23 (3.29\%) & 12 (1.71\%) &\o89 (22.25\%) \\
8 & 57 (8.14\%) & 27 (3.86\%) & 122 (30.50\%) \\
9 & 34 (4.86\%) & 22 (3.14\%) & 134 (33.50\%) \\
0 &\o9 (1.29\%) &\o6 (0.86\%) &\o59 (14.75\%) \\
\hline
total & 237 (3.39\%)  & 130 (1.86\%) & 943 (23.58\%)\\
\end{tabular}
\end{center}
\caption{Error cases on training sets}
\end{table*}

%\subsection{Tips}

\end{document}
