\documentclass[12pt]{article}
\usepackage{epsfig}
\usepackage{url}
\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[colorlinks]{hyperref}
\usepackage{fancyvrb}


\newcommand{\wc}[1]{\textit{todo: #1}}
\newcommand{\ct}[1]{\textit{cite: #1}}
\newcommand{\cd}[1]{\texttt{#1}}
\newcommand{\trm}[1]{\textit{#1}}
\newcommand{\vek}[1]{\textbf{#1}}

\newcommand{\loss}{\textit{L}}
\newcommand{\deriv}[2]{\frac{d{}#1}{d{}#2}}

\urldef\wikiurl\url{https://en.wikipedia.org/wiki/List_of_races_and_species_in_The_Hitchhiker%27s_Guide_to_the_Galaxy#Grebulons}

\title{Automatic Reverse-Mode Differentiation for Multilayer Perceptron}

\author{TAs: Tao Lin (\texttt{tao.lin@cs.cmu.edu}), \\ Rose (\texttt{rosecatherinek@cs.cmu.edu})}
\date{Out Oct 26, 2017\\Due Nov 7, 2017 via Autolab}

\begin{document}

\maketitle

\textbf{Prerequisite:} Please ensure you have first read Prof Cohen's notes on Automatic Reverse Mode Differentiation\footnote{\url{http://www.cs.cmu.edu/~wcohen/10-605/notes/autodiff.pdf}}. You can also refer to the sample code here\footnote{\url{http://www.cs.cmu.edu/~wcohen/10-605/code/sample-use-of-xman.py}}.

\textbf{Guidelines for Answers:} Please answer to the point. Please state any
additional assumptions you make while answering the questions. You need to
submit a tar file containing source files and a \textbf{pdf} version of report separately to autolab. 
Please make sure you write the report legibly for grading.


\textbf{Rules for Student Collaboration:} The purpose of student collaboration in solving assignments is to facilitate learning, not to circumvent it.
Studying the material in groups is strongly encouraged. It is allowed to seek
help from other students in understanding the material needed to solve a
homework problem, provided no written notes are taken or shared during
group discussions. The actual solutions must be written and implemented
by each student alone, and the student should be ready to reproduce their
solution upon request. You may ask clarifying questions on Piazza. However,
under no circumstances should you reveal any part of the answer publicly on
Piazza or any other public website. Any incidents of plagiarism or collaboration without full disclosure will be handled severely.


\textbf{Rules for External Help:} Some of the homework assignments used in
this class may have been used in prior versions of this class, or in classes at
other institutions. Avoiding the use of heavily tested assignments detracts
from the main purpose of these assignments, which is to reinforce the material
and stimulate thinking. Because some of these assignments may have been
used before, solutions to them may be available online or from other people.
It is explicitly forbidden to use any such sources or to consult people who have
solved these problems before. You must solve the homework assignments
completely on your own. We will mostly rely on your wisdom and honor
to follow this rule. However, if a violation is detected, it will be dealt with
harshly.

\begin{itemize}
	\item Did you receive any help whatsoever from anyone in solving this assignment? Yes/No
    \item If you answered yes, give full details:$\rule{6cm}{0.15mm}$
    (e.g. "Jane explained to me what is asked in Question 3.4" )
    \item Did you give any help whatsoever to anyone in solving this assignment? Yes/No
    \item If you answered yes, give full details:$\rule{6cm}{0.15mm}$
    (e.g. "I pointed Joe to section 2.3 to help him with Question 2" )
\end{itemize}

\newpage
\section{Overview}

% \wc{more hints: return delta[z]*d, to you can do the matrix-vector
%   thing; sometimes output is used in derivatives.}

In this assignment we will use an automatic differentiation system to implement a  Multilayer Perceptron (MLP) architecture for character level entity classification, using \texttt{python} and \texttt{numpy}.

Character level entity classification refers to determining the type of an entity 
given the characters which appear in its name as features. For example, given the name
``\cd{Antonio\_Veciana}" you might guess that it is a \cd{Person}, and given the name
``\cd{Anomis\_esocampta}" you might guess that it is a \cd{Species}. 
We will be learning to classify into the following 5 \cd{DBPedia} categories - \cd{Person}, \cd{Place}, \cd{Organisation}, \cd{Work}, \cd{Species}.

\section{Multilayer Perceptron}
\label{sec_mlp}
MLP is a simple neural network architecture consisting of multiple layers, each of 
which apply a linear transformation to their inputs followed by a non-linear mapping:
\begin{align*}
    o_i &= f(x^T w_i + b_i)
\end{align*}
Here $x \in \mathbb{R}^{d_{in}}$ is the layer input and $o_i \in \mathbb{R}$ is the 
$i$-th output of the layer. $w_i$, $b_i$ are layer parameters which will be optimized
during training. The number of outputs at each layer is called the \textit{dimension}
of that layer and we denote it by $d_{hid}$. We would like to use vector/matrix multiplications 
wherever possible to utilize their fast implementation in \texttt{numpy}, and combine the above
for all $i$ as:
\begin{equation*}
    o = f(x^T W + b)
\end{equation*}
$W=[w_1,w_2,\ldots,w_{d_{hid}}] \in \mathbb{R}^{d_{in} \times d_{hid}}$ stacks all the weight vectors 
horizontally, and $b \in \mathbb{R}^{d_{hid}}$ holds all the biases. The non-linearity $f$ is
applied elementwise.

To further speed-up the computation we can process a minibatch of inputs together. Let $X \in \mathbb{R}^{N \times d_{in}}$
be a matrix holding $N$ examples row-wise. We can compute the layer outputs for all of these together:
\begin{equation}
    O = f(X W + B)
\end{equation}
$B = \mathbf{1} \otimes b^T \in \mathbb{R}^{N \times d_{hid}}$ is a ``broadcasted" version of the bias
of appropriate dimensions. For this assigment we will use \cd{numpy} for all matrix operations, which takes care
of broadcasting automatically (see here\footnote{\url{https://docs.scipy.org/doc/numpy/user/basics.broadcasting.html}}
for details), hence we can use the vector $b$ directly.
% \begin{verbatim}
% import numpy as np
% Y = np.dot(X.transpose(), W) + b
% O = elemwise_nonlinear_func(Y).transpose()
% \end{verbatim}
The nonlinearity we will use is the \texttt{Rectified Linear Unit (ReLU)}:
\begin{equation*}
    f(x) = 
    \begin{cases}
        x &\quad x>0 \\
        0 &\quad x\leq0
    \end{cases}
\end{equation*}
For vectors the nonlinearity is applied element-wise, and we can again use numpy broadcasting for
this. In multi-layer networks, output of layer $k$ is passed as input to layer $k+1$:
\begin{equation}
O^{(k+1)} = f(O^{(k)}W^{(k)} + b^{(k)})
\end{equation}
% \begin{verbatim}
% def relu(X):
% 	# X can be arbitrary shape
%     return np.maximum(0,X) 
% \end{verbatim}

We can set output size of the last layer of the MLP to produce a vector the same size as the number of
labels $C$ in our dataset. The operations described thus far map inputs to positive reals, but for 
classification tasks we are interested 
in obtaining a \textit{distribution} over class labels. This is usually done by
passing the output of the last layer through a \texttt{softMax} operation:
\begin{equation*}
    p_j = \frac{e^{o_j}}{\sum_{j'=1}^C e^{o_{j'}}}
\end{equation*}
Note that $p$ defines a valid distribution, and elements of $o$ which have a
high relative value will have a high probability in $p$. In case $o_j$s are very large or very negative there might be numerical issues in computing the above. A more numerically stable version of softMax uses the following:
\begin{equation}
    \label{eq:softMax}
    p_j = \frac{e^{o_j-a}}{\sum_{j'=1}^C e^{o_{j'}-a}}
\end{equation}
This is true for any $a$; we will use $a=\max_j o_j$. Lastly, we need to define a loss function which measures how far the output  distribution $p_i$ for input $i$ is from its target distribution $t_i$. We will use the cross-entropy loss for this:
\begin{equation}
\label{eq:xentropy}
l_i = - \sum_{j=1}^C t_{i}^{(j)} \log p_{i}^{(j)}
\end{equation}
For single-label classification, $t_i$ is a $C$-dimensional one-hot vector encoding the correct label for this example. The above equations compute $p$ and $l$ for a single $o$, but in your code you should use \texttt{numpy}
operations to compute a minibatch of distributions $P$ and losses $L$ from a minibatches of $O$.
The objective function we will optimize is the average of losses across a minibatch:
\begin{equation}
    \label{eq:loss}
    \text{loss} = \frac{1}{N} \sum_{i=1}^N l_i
\end{equation}
Now we can take gradients of $\text{loss}$ wrt to the parameters of the network and perform
Stochastic Gradient Descent (SGD).

To summarize, the architecture you will implement for this assignment consists of a MLP
with one hidden layer, followed by a softMax layer (\ref{eq:softMax}) and cross-entropy loss 
(\ref{eq:xentropy}).
Given an input minibatch $X$ and their associated targets $T$, the output $P$ and loss is computed as:
\begin{align*}
    O^{(1)} &= \text{relu}(X W^{(1)} + b^{(1)}) \\
    O^{(2)} &= \text{relu}({O^{(1)}} W^{(2)} + b^{(2)}) \\
    P &= \text{softMax}(O^{(2)}) \\
    \text{loss} &= \text{mean}(\text{crossEnt}(P,T))
\end{align*}



\subsection{Learning}
Parameters of the above network can be trained using minibatch SGD. Once the loss function is defined we can take its derivative wrt to any parameter $w_{ij}$ and update it as follows:
\begin{equation}
w_{ij}^{(k)} \leftarrow w_{ij}^{(k-1)} - \lambda \deriv{\text{loss}}{w_{ij}}
\end{equation}
$\lambda$ is the learning rate.
In this assignment, you are not required to modify the learning rate as the training proceeds. 

\section{Autodiff Implementation}
In the starter code the following files are given - 
\begin{itemize}
\item \cd{xman.py} -- classes for expression manager, registers and operations
\item \cd{utils.py} -- classes for data preprocessing and forming minibatches (more on this below)
\item \cd{mlp.py} -- you need to implement the mlp here
\item \cd{functions.py} -- function definitions and their gradients are declared here. You need to add definitions of the required forward and backward pass functions (more on this below)
\item \cd{autograd.py} -- class for forward and backward propagation over a Wengert list
\end{itemize}
Here we briefly outline the steps needed to implement a model using the package provided with the handout. 

\subsection{Declare operations, their functions and gradients} 
First we must declare all the primitive operations our function uses in the \cd{XManFunctions} class. For example, to declare \cd{relu}, add the following lines to \cd{f} class in \cd{functions.py}:
\begin{verbatim}
class f(XManFunctions):
    @staticmethod
    def relu(a):
        return XManFunctions.registerDefinedByOperator('relu',a)                             
\end{verbatim}
\cd{add}, \cd{mul} and \cd{subtract} are decalred by default in \cd{XManFunctions}.

Next we need to define functions for both the forward and backward pass for each of the operators in our definition. The following example shows the definitions for \cd{add}:

\begin{verbatim}
import numpy as np
# forward pass
EVAL_FUNS = {
    'add':      lambda x1,x2: x1+x2,
	}
    
def _derivAdd(delta,x1):
    if delta.shape!=x1.shape:
        # broadcast, sum along axis=0
        return delta.sum(axis=0)
    else: return delta

# backward pass
BP_FUNS = {
    'add':    	[lambda delta,out,x1,x2: _derivAdd(delta,x1),    
                     lambda delta,out,x1,x2: _derivAdd(delta,x2)],
    }
\end{verbatim}
Lets take a closer look at what is happening here. \cd{EVAL\_FUNS} is a dictionary whose keys are the names of the operators as declared in the previous section and values are the actual functions themselves (usually defined using lambda calculus). \cd{BP\_FUNS} is another dictionary with the same set of keys as \cd{EVAL\_FUNS}, but whose value for a key is a list of functions each computing its gradient wrt one of its inputs. 

In the above example \cd{BP\_FUNS[`add'][0]} computes the derivative wrt \cd{x1}, and \cd{BP\_FUNS[`add'][1]} computes the derivative wrt \cd{x2}. As input each of these functions receives:
\begin{itemize}
\item \cd{delta} - partial derivative of the output of this operation
\item \cd{out} - output of this operation in the forward pass. This can be sometimes useful for computing the derivative. For example, for the sigmoid nonlinearity $\sigma'(x)=\sigma(x)(1-\sigma(x))$.
\item \cd{x1},\cd{x2},... - all inputs to the operation
\end{itemize}

Some things to be careful about:
\begin{enumerate}
\item Remember that our functions need to run in minibatch mode, where they receive matrices as input and produce matrices as output. 
\item Ensure that the shape of a gradient matches the shape of the input wrt it is computed. As an example consider matrix multiplication $M=A\cdot B$ where $A$ is $n \times m$ $B$ is $m \times k$, then both $M$ and the backpropagated derivative of the loss w.r.t. $M$ ($\deriv{\text{loss}}{M}$) will be $n \times k$. To get the partial derivates of the loss w.r.t. $A$ and $B$:
\begin{align*}
\deriv{\text{loss}}{A} &= \deriv{\text{loss}}{M} \cdot B^T\\
\deriv{\text{loss}}{B} &= A^T \cdot \deriv{\text{loss}}{M}
\end{align*}
In our code $\deriv{\text{loss}}{M}$ will be stored in \cd{delta[M]}. \\
One of the common pitfalls is mismatched shapes of the gradient and the input variable. To debug, you could change the \texttt{TRACE\_EVAL} and/or \texttt{TRACE\_BP} flags in \texttt{autograd.py} and check if the shapes of the variables are as expected in each step. 
\item Be careful about \cd{numpy} broadcasting. An example of this is shown in \cd{\_derivAdd}. In numpy if we add a $N \times d$ matrix and a size $ d$ vector, the vector is broadcasted to the size of the matrix. In this case the gradient coming back will be size $N \times d$, and needs to be summed along the first dimension for the vector (but not for the matrix!). This happens for example when we write $X W + b$.
\item \cd{autograd.py} (described below) has an optimization which combines the backward pass for \cd{crossEnt} and \cd{softMax} operations. The gradients of this combined operation are easier to compute than the individual ones. So you need to implement \cd{BP\_FUNS} only for the combined operation \cd{crossEnt-softMax}, but implement them separately in \cd{EVAL\_FUNS}. \\
Note:
\begin{itemize}
    \item Make sure that your cross entropy function in \cd{EVAL\_FUNS} is named as \cd{crossEnt}, and your softmax function is named as \cd{softMax}, for the optimization to work. 
    \item The definition of the derivative of the optimized call in \cd{BP\_FUNS} has to be named as \cd{crossEnt-softMax}, because that is the term the optimizer will use.
\end{itemize}
\item Unit tests for function definitions and their gradients are included in \cd{functions.py} to help you debug your implementation faster. You can run \cd{python functions.py} to check your implementation.
\end{enumerate}

\subsection{Describe the Model}
Once the primitive operations are defined, we can go ahead and define the model. First we need to declare registers to hold inputs and parameters. Suppose there is one input \cd{x}, a target \cd{y} and two parameters \cd{W} and \cd{b}:
\begin{verbatim}
W = f.param(name='W', default=a*np.random.uniform(-1.,1.,(10,10))
b = f.param(name='b', default=0.1*np.random.uniform(-1.,1.,(10,))
x = f.input(name='x', default=np.random.rand(1,10))
y = f.input(name='y', default=np.random.rand(1,10))
\end{verbatim}
You \textbf{must} specify the \cd{name} and \cd{default} fields for each register, including \cd{input} registers! The \cd{name} is used during the forward and backward passes to bind values to the correct register (more on this later). The \cd{default} value is used as initialization for parameters and also for performing gradient checks. We will use the \cd{inputDict} method described in the next section to collect values for all registers and perform gradient checking using that. For this purpose, you can assign any random default value to the \cd{input} registers, as long as it is the right shape. \\

\noindent\textbf{Note on initialization of parameters:} As discussed in class, it is important to initialize parameters such that intermediate values in the network do not lie in the saturated regions of the non-linearity. One good heuristic is to sample the weights for $W$ of size $d_{in} \times d_{out}$ from a uniform distribution $\mathcal{U}[-a,a]$ whose scale $a$ is given by:
\begin{equation}
a = \sqrt[]{\frac{6}{d_{in} + d_{out}}}
\end{equation}
This is called Glorot initialization\footnote{\url{http://jmlr.org/proceedings/papers/v9/glorot10a/glorot10a.pdf}}. Bias terms can be initialized at a scale of 0.1.

Now write the model in terms of primitive operations:
\begin{verbatim}
xm = XMan()
xm.o1 = f.relu( f.mul(x,W) + b )
...
xm.loss = ...
my_xman = xm.setup()
\end{verbatim}
We can construct the Wengert list for any register in \cd{my\_xman} by calling \cd{operationSequence()}. 
\begin{verbatim}
# wengert list for the `loss' register
wengert_list = my_xman.operationSequence(my_xman.loss)
\end{verbatim}

\subsection{Forward / Backward Pass}
Another useful method in the \cd{XMan} class is \cd{inputDict()}, which returns a dictionary containing default values associated with its registers:
\begin{verbatim}
valueDict = my_xman.inputDict()
# valueDict contains register names as keys
# and defaults as values
\end{verbatim}
At the beginning of training we will call \cd{inputDict} to collect initial values of all parameters (\cd{valueDict} also contains default values for the data, but we will overwrite this). Then we will iterate through minibatches of the data (more on this below), write the inputs to \cd{valueDict} and perform updates.

One update consists of propagating data and parameters through the Wengert list to get the outputs, and backpropagating gradients to get the updates for all parameters. The \cd{Autograd} class in \cd{autograd.py} provides helper functions to do this.
\begin{verbatim}
# valueDict contains current value of params
# xc and yc are inputs for current minibatch
valueDict[`x'] = xc
valueDict[`y'] = yc
ad = Autograd(my_xman)
valueDict = ad.eval(wengert_list, valueDict) # forward pass
gradients = ad.bprop(wengert_list, valueDict, 
                      loss=np.float_(1.))    # backward pass
\end{verbatim}
The last argument specifies gradient of the loss which will be backpropagated. \cd{gradients} is a dictionary whose keys are register names and values are gradients. These can be used to apply updates to the parameters as follows:
\begin{verbatim}
for rname in grads:
    if my_xman.isParam(rname):
        valueDict[rname] = # do this yourself
\end{verbatim}

\subsection{Gradient Checking}
How do we check if our implementation is correct? One way to do that is gradient checking. Recall from calculus that for any function $J(\theta)$:
\begin{equation}
\deriv{J(\theta)}{\theta} = \lim_{\epsilon\to 0}\frac{J(\theta+\epsilon)-J(\theta-\epsilon)}{2\epsilon}
\end{equation}
Thus for any specific value of a parameter $\theta$ we can numerically approximate the right hand side above by evaluating loss of the network at $\theta+\epsilon$ and $\theta-\epsilon$. For small $\epsilon$ the numerical gradient should match the one computed using autodiff. You can use $\epsilon=10^{-4}$ and check if gradients match up to 3 decimal places. 

\section{Data}
For this assignment you need to predict the category label of a DBPedia entity based on its title. The data format is \textbf{different} from the earlier assignments. The data contains two columns separated by
tab, with the title in the first column and label in second.
\begin{verbatim}
Lloyd_Stinson   Person
Lobogenesis_centrota    Species
Loch_of_Craiglush   Place
\end{verbatim}


We will encode entities for input to the networks by converting characters to a one-hot representation. Suppose we have a dictionary mapping each character in the data to an index \cd{chardict = \{`a':1,`b':2...\}} and the total number of characters in the dataset is $V$, then we will represent \cd{`a'} as a $V$-dimensional vector $[1,0,0,\ldots,0]$, and \cd{`b'} as another $V$-dimensional vector $[0,1,0,\ldots,0]$. A string of characters will be encoded to a matrix whose each row is a $V$-dimensional vector.

We will fix the maximum length of an entity to $M$, longer entities will be truncated to this length, and shorter ones will be padded with white-space. We have provided you with code that preprocesses the data and divides it into minibatches in \cd{utils.py}. You can,
\begin{verbatim}
from utils import *
# load data and preprocess
dp = DataPreprocessor()
data = dp.preprocess(<training_file>, <validation_file>, 
       <testing_file>)
# minibatches
mb_train = MinibatchLoader(data.training, batch_size, max_len, 
           len(data.chardict), len(data.labeldict))
mb_valid = MinibatchLoader(data.validation, len(data.validation), 
           max_len, len(data.chardict), len(data.labeldict), 
           shuffle=False)
mb_test = MinibatchLoader(data.test, len(data.test), max_len, 
           len(data.chardict), len(data.labeldict), shuffle=False)
\end{verbatim}
\cd{max\_len} is the maximum length $M$ which we set. \cd{shuffle=True/False} tells the batch loader whether to shuffle the data after every epoch. For validation and test sets we set the batch size same as the size of the dataset. You can then iterate over the data using,
\begin{verbatim}
for (idxs,e,l) in mb_train:
    # idxs - ids of examples in minibatch
    # e - entities in one-hot format
    # l - corresponding output labels also in one-hot format
\end{verbatim}
After every epoch (full sweep through \cd{mb\_train}) the data is shuffled for the next epoch in \cd{mb\_train}. \cd{idxs} has shape $N$, e has shape $N \times M \times V$ and l has shape $N \times C$ where $N$ is the batch size. Make sure that this makes sense to you.

For input to the MLP we will concatenate all the one-hot encodings into one row vector, so you will need to flatten \cd{e} to a $N \times MV$ size matrix whose each row consists of the encoding of all characters in the entity one after the other. You can use \cd{numpy.reshape} for this. 

You are given two datasets for this assignment - \cd{tiny} for debugging, and \cd{smaller} for reporting results. The \cd{Data} and \cd{MiniBatchLoader} classes create dictionaries for all characters and labels in the dataset and use that to encode the inputs and labels into a one-hot vector format.

A validation file (*.valid files) is provided to prevent overfitting. You should evaluate the loss function on the validation dataset after every epoch and store the parameters of the best model in a separate dictionary. Then after training is completed, use these best parameters to make predictions on the test set. Remember you should not do backpropagation on the validation dataset. For reporting the results you use test (*.test) files.

You can get the data from 
\begin{verbatim}	
https://drive.google.com/open?id=0B58rr945j04BcGctanY1UHVFZVE
\end{verbatim}

For the evaluation on Autolab we will run your code on a separate train, validation and testing dataset \cd{autolab} with a specific set of params as command line arguments. 
%This is smaller than the \cd{smaller} dataset provided to you, so you should be careful about overfitting.

\section{Deliverables}

You need to write code for building, training and evaluating an MLP in \cd{mlp.py}.
You need to write your function definitions and their derivatives in \cd{functions.py}.
Make sure that you call the final predicted labels as \cd{outputs} and the loss function as \cd{loss} in the \cd{XMan} object. You should also remember to initialize the default parameters and inputs. Otherwise you'd get zero score on our gradient checking code.\\
You should run your code using the following defaults:
\begin{Verbatim}[commandchars=\\\{\}]
python mlp.py --max_len 10 --num_hid 50
               --batch_size 64 --dataset small 
               --epochs 15 --init_lr 0.5 
               --output_file output 
               --train_loss_file train_loss
\end{Verbatim}
In autolab we will call the main function in \cd{mlp.py} and pass a dictionary of hyperparameter values. We will check your code for gradient correctness, training loss trend, mean Loss on the test output,  implementation of function definitions and derivates, and speed compared to the benchmark code written by us. 

The training loss you obtain after each iteration on the \cd{batch\_size}d data (not epoch) should be stored in the file specified by \cd{--train\_loss\_file} in numpy format using \cd{np.save()}. 
Your final output probabilities should be stored in the file specified by \cd{--output\_file}  in numpy format using \cd{np.save()} in the same row order as the input test file.  Tar the following files for submission.
\begin{itemize}
\item mlp.py (This file would contain the MLP class and the main file with the default params)
\item functions.py (This file would contain the function definitions and their gradients)
\item Any other helper files
\end{itemize}
Tar the files directly using the command below. Do NOT put the
above files in a folder and then tar the folder. You do not need to upload the saved temporary files.
\begin{verbatim}
tar -cvf hw4.tar mlp.py functions.py
\end{verbatim}

Also, please do not forget to submit your report \cd{hw4.pdf} via the HW4: Report link in Autolab.
% \subsection{ Extra Credit}

% You'll receive extra credit if your approach's loss is significantly better than our approach. You can experiment with different layer sizes, different learning rates, different activations or even different number of layers or anything which you feel will give you a better accuracy. Be sure to describe your results and approach for this in the report.

\section{Questions}
\begin{enumerate}
\item Plot the average training time per epoch for MLP for batch size $N=\{16,32,64\}$, and default values of remaining hyperparameters. What trends do you observe?

\item Plot the average training time per epoch for MLP for maximum input length $M=\{10,15,20\}$, and default values for remaining hyperparameters. What trends do you observe?


\item Given feature vectors for tokens in a query $q_1,q_2,\ldots q_M$ and feature vectors for tokens in a document $d_1,d_2,\ldots d_N$, where $q_i, d_j \in \mathbb{R}^n \quad\forall i,j$, the \textit{soft-attention} distribution of $i$th query token over the document is given by:
\begin{equation}
\alpha^{(i)}_j = \frac{\exp{q_i^Td_j}}{\sum_{j'}\exp{q_i^Td_{j'}}} \qquad j=1,\ldots N
\end{equation}
Given a $M \times n$ matrix $Q$ and an $N \times n$ matrix $D$ holding all the query and document feature vectors respectively, write the steps needed to compute all the attention distributions for $i=1,\ldots M$, using only matrix operations. You can use broadcasting, and assume that efficient implementations of \cd{row-sum} and \cd{exp} are given.


\item Consider a single-layer MLP without bias which computes $f=\text{tanh}(\sum_{i=1}^{1000} x_i w_i)$ where $x_i,w_i\geq0 \quad i=1,\ldots 1000$. Recall that $\tanh(x)$ looks like:
\begin{figure}[h!]
\centering
%\includegraphics[width=0.6\linewidth]{tanh_zoom60.jpg}
\end{figure}

We initialize the weights $w_i \sim \mathcal{U}[0,a]$. Determine the scale $a$ for the following inputs:
\begin{itemize}
\item One-hot -- $x_i = 1$ for $i=i_0$ and $x_i = 0$ for $i\neq i_0$.
\item Small -- $x_i \in [0,1]$ for all $i$.
\item Big -- $x_i \in [1000,1001]$ for all $i$.
\end{itemize}

\end{enumerate}

\section{Marking breakdown}
\begin{itemize}
\item Report Questions - 30 points
\end{itemize}

\end{document}


\end{enumerate}

\section{Grading Scheme}
\begin{itemize}
\item Code Correctness (gradient check)\footnote{\textbf{Reminder} - You must name the loss register as ``\cd{loss}'' for our gradient checking to work} - 20 points
\item Code Correctness (training loss check) - 10 points
\item Code Correctness (unit tests on function implementation) - 10 points
\item Code Accuracy (loss on held-out test set) - 15 points
\item Code Speed - 15 points
\item Report Questions - 30 points
\end{itemize}

\end{document}

