\documentclass[12pt]{article}

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

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

\def\w{\mathbf{w}}
\def\x{\mathbf{x}}
\def\y{\mathbf{y}}
\def\z{\mathbf{z}}
\def\U{\mathbf{U}}
\def\transpose{\top}
\section{Adapting Centres in Radial Basis Networks (2\%)}
\begin{itemize}
\item
\begin{eqnarray*}
\frac{\partial E}{\partial\z_k} & \propto &
\frac{\partial}{\partial\z_k} \sum_n (y_n-\sum_jw_jh_j(\x_n))^2
\\ & = &
\sum_n2(y_n-\sum_jw_jh_j(\x_n))
\frac{\partial}{\partial\z_k}
w_k \exp(-\alpha_k(\x_n-\z_k)^{\transpose}(\x_n-\z_k))
\\ & = &
\sum_n2(y_n-\sum_jw_jh_j(\x_n))
w_k \exp(-\alpha_k(\x_n-\z_k)^{\transpose}(\x_n-\z_k)).2\alpha_k(x_n-z_k)
\\ & = &
4w_k\alpha_k \sum_n
(y_n-\sum_jw_jh_j(\x_n)).h_k(\x_n)(\x_n-\z_k)
\end{eqnarray*}

\item
\begin{eqnarray*}
\frac{\partial E}{\partial\log\alpha_k} & \propto &
\frac{\partial}{\partial\log\alpha_k}
\sum_n(y_n-\sum_jw_jh_j(\x_n))^2
\\ & = &
\sum_n2(y_n-\sum_jw_jh_j(\x_n))^2
\frac{-\partial}{\partial\log\alpha_k}
w_kh_k(\x_n)
\\ & = &
\sum_n2(y_n-\sum_jw_jh_j(\x_n))^2
\frac{-\partial}{\partial\log\alpha_k}
w_k\exp\left( -e^{\log\alpha_k}(\x_n-\z_k)^\transpose(\x_n-\z_k) \right)
\\ & = &
\sum_n2(y_n-\sum_jw_jh_j(\x_n))^2
w_k\exp\left( -\alpha_k(\x_n-\z_k)^\transpose(\x_n-\z_k) \right)
  .(\x_n-\z_k)^2
\\ & = &
2\alpha_kw_k\sum_n (y_n-\sum_jw_jh_j(\x_n)).h_k(\x_n).(\x_n-\z_k)^2
\end{eqnarray*}
\end{itemize}


\newpage
\section{Pseudo-Bayesian Linear Regression (4\%)}
\begin{itemize}
\item
We start computing $p(\w|\{\x_n,y_n\},a,b)$.  Since this is a 
probability distribution, we forget about constants (including the
    denominator) and finally
adjust the solution to sum to one.
\begin{eqnarray*}
p(\w|\{\x_n,y_n\},a,b) & = &
\frac{p(\{\x_n,y_n\}|\w)p(\w)}{p(\{\x_n,y_n\})}
\\ & \propto &
\prod_n p(\x_n,y_n|\w)p(\w)
\\ & \propto &
\exp\left\{\frac{-1}{2b}\sum_n(y_n-\w^\transpose\x_n)^2 -\frac1{2a}\w^2
\right\}
\\ & \propto &
\exp\left\{\frac{-1}2\left(
\w^\transpose(\frac{\mathbf{I}}a+\frac{\sum_n\x_n\x_n^\transpose}b)\w
-2\sum_ny_n\w^\transpose\x_n
\right)\right\}
\end{eqnarray*}
Now it looks like a gaussian with covariance and mean:
$$\Sigma_\w = (\frac{\mathbf{I}}a + \frac{\sum_n\x_n\x_n^\transpose}b)^{-1}$$
$$\mu_\w = \sum_ny_n\x_n\Sigma_\w$$
So:
$$
p(\w|\{\x_n,y_n\},a,b) = {\cal N}(\w,\mu_\w,\Sigma_\w).
$$

\item
We differentiate to find the optimal weights:
\begin{eqnarray*}
\frac{\partial}{\partial\w}\cdot & = &
2\lambda\w - \sum_n2(y_n-\w^\transpose\x_n)\x_n
\end{eqnarray*}


\end{itemize}

\newpage
\section{Regularizing Linear Mixtures of Experts (2\%)}
\begin{itemize}
\item
\begin{eqnarray*}
\partial\ell^{\mathit{new}}/\partial\U_j & = &
\sum_n \frac
{p(j|\x_n)\partial/\partial\U_j\left[exp(-\frac12(\y_n-\U_j\x_n)^{\transpose}
\Sigma^{-1} (\y_n-\U_j\x_n)  \right]}
{\sum_j p(j|\x_n) p(\y_n|j,\x_n)}
+\partial/\partial\U_j(\lambda \sum_{ijk}U_{ijk}^2)
\\
& = &
\sum_n \frac
{p(j|\x_n)p(\y_n|j,\x_n)\Sigma^{-1}(\y_n|\U_j,\x_n)\x_n}
{\sum_j p(j|\x_n) p(\y_n|j,\x_n)}
+2\lambda\sum_{ik}U_ijk\frac\partial{\partial\U_j}(U_{ijk})
\\
& = & \Sigma^{-1}\sum_np(j|\x_n,\y_n)(\y_n-\U_j\x_n)\x_n + 2\lambda\U_j
\end{eqnarray*}
The last part is deduced by observing that
$\frac\partial{\partial\U_j}U_{ijk}$
is a matrix of all zeros with a one at entry $(i,k)$.

\item
To regularize the individual experts, another way is to use ridge regression
with each gaussian.  Means:
$$
\ell = \sum_n\log\sum_j
\left[p(j|\x_n){\cal N}(\y_n;\U_j\x_n,\Sigma)+\lambda_j\sum_{ik}U_{ijk}^2  \right]
$$

To regularize the gate, we add $\epsilon\sum v_j^2$ to the cost function:
$$
\ell = \sum_n\log\sum_j
p(j|\x_n){\cal N}(\y_n;\U_j\x_n,\Sigma)+\epsilon\sum_{j}v_j^2
$$

To regularize the whole architecture, we add some
randomly generated pairs of inputs and output
$(x_i,y_i)$,
considering the range of each variable when generating them.
\end{itemize}


\newpage
\section{Fully Observed Trees (10\%)}
\noindent
Min log likelihood: -99.57562\\
Max log likelihood: -5.32291\\
Mean log likelihood: -14.69724\\
Median log likelihood: -12.89544\\
Worst log likelihood belongs to document number 10576\\
This document has words: \texttt{car computer course data disk display earth evidence
fact files ftp god health help hit human image launch lunar mars mission moon
nasa number orbit power program research satellite science solar space studies
system technology version war water world}
\begin{center}
\vfill
\smash
{\includegraphics[width=\textwidth]{code/likelihood.pdf}}
\newpage
\includegraphics[width=\textwidth,height=\textheight]{code/treeu.pdf}
\newpage
\rotatebox{-90}{
\includegraphics[width=\textheight,height=.8\textwidth]{code/treed.pdf}
}
\end{center}

\end{document}