\documentclass{article} \usepackage[margin=1in]{geometry} \usepackage{amsmath, amsfonts} \usepackage{enumerate} \usepackage{graphicx} \usepackage{titling} \usepackage{url} \usepackage{xcolor} \usepackage{xfrac} \usepackage[colorlinks=true,urlcolor=blue]{hyperref} % \usepackage{minted} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Commands for customizing the assignment % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand \outdate {November 2, 2016} \newcommand \duedate {5:30 p.m. Monday, November 21, 2016} \title{ Homework 6: Deep Learning \\ \vspace{0.2cm} \large { 10-601B: Machine Learning (Fall 2016) \\ Out \outdate{} \\ Due \duedate{} } } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Useful commands for typesetting the questions % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand \expect {\mathbb{E}} \newcommand \mle [1]{{\hat #1}^{\rm MLE}} \newcommand \map [1]{{\hat #1}^{\rm MAP}} \newcommand \argmax {\operatorname*{argmax}} \newcommand \argmin {\operatorname*{argmin}} \newcommand \code [1]{{\tt #1}} \newcommand \datacount [1]{\#\{#1\}} \newcommand \ind [1]{\mathbb{I}\{#1\}} %%%%%%%%%%%%%%%%%%%%%%%%%% % Document configuration % %%%%%%%%%%%%%%%%%%%%%%%%%% % Don't display a date in the title and remove the white space \predate{} \postdate{} \date{} % Don't display an author and remove the white space %\preauthor{} %\postauthor{} \author{TAs: Pradeep Dasigi, Varshaa Naganathan, Sriram Vasudevan} %%%%%%%%%%%%%%%%%% % Begin Document % %%%%%%%%%%%%%%%%%% \begin{document} \maketitle \section*{Instructions} \begin{itemize} \item {\bf Late homework policy:} Homework is worth full credit if submitted before the due date, half credit during the next 48 hours, and zero credit after that. \item {\bf Submission:} You must submit your code for questions 2-9, 12, 13 and 15 on time electronically by submitting to autolab by \duedate{}. On the Homework 5 autolab page, you can click on the ``download handout'' link to download the submission template, which is a tar archive containing a Octave \code{.m} file for each programming question. Replace each of these files with your solutions for the corresponding problem, create a new tar archive of the top-level directory, and submit your archived solutions online by clicking the ``Submit File'' button. \textbf{\emph{DO NOT}} change the name of any of the files or folders in the submission template. In other words, your submitted files should have exactly the same names as those in the submission template. Do not modify the directory structure. For questions 1, 10, 11 and 14, submit your written answers on Gradescope. \item \textbf{Collaboration policy}: Please read the policy on the course webpage: \url{http://www.cs.cmu.edu/~mgormley/courses/10601b-f16/about.html} \end{itemize} In this assignment, we are going to implement a Convolution Neural Network (CNN) to classify hand written digits of MNIST \footnote{\url{http://yann.lecun.com/exdb/mnist/}} data. Since the breakthrough of CNNs on ImageNet classification~\cite{krizhevsky2012imagenet}, CNNs have been widely applied and achieved the state the art of results in many areas of computer vision. The recent AI programs that can beat humans in playing Atari game~\cite{mnih2015human} and Go~\cite{silver2016mastering} also used CNNs in their models. We are going to implement the earliest CNN model, LeNet~\cite{lecun1998gradient}, that was successfully applied to classify hand written digits. You will get familiar with the workflow needed to build a neural network model after this assignment. The Stanford CNN course\footnote{\url{http://cs231n.github.io/}} and UFLDL\footnote{\url{http://ufldl.stanford.edu/tutorial/}} material are excellent for beginners to read. You are encouraged to read some of them before doing this assignment. \section{Convolutional Neural Networks (CNN)} We begin by introducing the basic structure and building blocks of CNNs. CNNs are made up of layers that have learnable parameters including weights and bias. Each layer takes the output from previous layer, performs some operations and produces an output. The final layer is typically a softmax function which outputs the probability of the input being in different classes. We optimize an objective function over the parameters of all the layers and then use stochastic gradient descent (SGD) to update the parameters to train a model. Depending on the operation in the layers, we can divide the layers into following types: \subsection{Inner product layer (fully connected layer)} As the name suggests, every output neuron of inner product layer has full connection to the input neurons. The output is the multiplication of the input with a weight matrix plus a bias offset, i.e.: \begin{equation} f(x) = Wx + b. \end{equation} This is simply a linear transformation of the input. The weight parameter $W$ and bias parameter $b$ are learnable in this layer. The input $x$ is $d$ dimensional column vector, and $W$ is a $d\times n$ matrix and $b$ is $n$ dimensional column vector. \subsection{Activation layer} We add nonlinear activation functions after the inner product layers to model the non-linearity of real data. Here are some of the popular choices for non-linear activation: \begin{itemize} \item \textbf{Sigmoid}: $\sigma(x) = \frac{1}{(1+e^{-x})}$ \item \textbf{tanh}: $\text{tanh}(x) = \frac{(e^{2x} - 1)}{(e^{2x} + 1)}$ \item \textbf{ReLU}: $\text{relu}(x) = \max(0, x)$ \end{itemize} Rectified Linear Unit (ReLU) has been found to work well in vision related problems. There is no learnable parameters in the ReLU layer. In this homework, you will use ReLU, and a recently proposed modification of it called Exponential Linear Unit (ELU). Note that the activation is usually combined with inner product layer as a single layer, but here we separate them in order to make the code modular. \subsection{Convolution layer} The convolution layer is the core building block of CNNs. Unlike the inner product layer, each output neuron of a convolution layer is connected only to some input neurons. As the name suggest, in the convolution layer, we apply convolution operations with filters on input feature maps (or images). In image processing, there are many types of kernels (filters) that can be used to blur, sharpen an image or detect edges in an image. Read the Wikipedia page\footnote{\url{https://en.wikipedia.org/wiki/Kernel_(image_processing)}} page if you are not familiar with the convolution operation. In a convolution layer, the filter (or kernel) parameters are learnable and we want to adapt the filters to data. There is also more than one filter at each convolution layer. The input to the convolution layer is a three dimensional tensor (and is often referred to as the \textbf{input feature map} in the rest of this document), rather than a vector as in inner product layer, and it is of the shape $h \times w \times c$, where $h$ is the height of each input image, $w$ is the width and $c$ is the number of channels. Note that we represent each channel of the image as a different slice in the input tensor. Fig.~\ref{fig:cnn} shows the detailed convolution operation. The input is a feature map, i.e., a three dimensional tensor with size $h\times w\times c$. The convolution operation involves applying filters on this input. Each filter is a sliding window, and the output of the convolution layer is the sequence of outputs produced by each of those filters during the sliding operation. Let us assume each filter has a square window of size $k\times k$ per channel, thus making filter size $k \times k \times c$. We use $n$ filters in a convolution layer, making the number of parameters in this layer $k\times k \times c \times n$. In addition to these parameters, the convolution layer also has two hyper-parameters: the padding size $p$ and stride step $s$. In the sliding window process described above, the output from each filter is a function of a neighborhood of input feature map. Since the edges have fewer neighbors, applying a filter directly is not feasible. To avoid this problem, inputs are typically padded (with zeros) on all sides, effectively making the the height and width of the padded input $h + 2p$ and $w + 2p$ respectively, where $p$ is the size of padding. Stride ($s$) is the step size of convolution operation. As Fig.~\ref{fig:cnn} shows, the red square on the left is a filter applied locally on the input feature map. We multiply the filter weights (of size $k\times k\times c$) with a local region of the input feature map and then sum the product to get the \textbf{output feature map}. Hence, the first two dimensions of output feature map is $[(h+2p-k)/s + 1] \times [(w+2p-k)/s + 1 ]$. Since we have $n$ filters in a convolution layer, the output feature map is of size $[(h+2p-k)/s + 1] \times [(w+2p-k)/s + 1] \times n $. For more details about the convolutional layer, see Stanford's course on CNNs for visual recognition \footnote{\url{http://cs231n.github.io/convolutional-networks/}}. \subsection{Pooling layer} It is common to use pooling layers after convolutional layers to reduce the spatial size of feature maps. Pooling layers are also called down-sample layers, and perform an aggregation operation on the output of a convolution layer. Like the convolution layer, the pooling operation also acts locally on the feature maps. A popular kind of pooling is max-pooling, and it simply involves computing the maximum value within each feature window. This allows us to extract more salient feature maps and reduce the number of parameters of CNNs to reduce over-fitting. Pooling is typically applied independently within each channel of the input feature map. \begin{figure}[!t] \includegraphics[width=0.6\linewidth]{figures/cnn.pdf} \centering \caption{convolution layer} \label{fig:cnn} \end{figure} \begin{enumerate}[Q1] \item \textbf{[5 points]} Does pooling make the model more or less sensitive to small changes in the input images? Why? By small changes, we mean moving the input images to the left or right, rotating them slightly etc. \end{enumerate} \subsection{Loss layer} For classification task, we use a softmax function to assign probability to each class given the input feature map: \begin{equation} p = \text{softmax}(Wx+b). \end{equation} In training, we know the label given the input image, hence, we want to minimize the negative log probability of the given label: \begin{equation} l = -\log(p_{j}), \end{equation} where $j$ is the label of the input. This is the objective function we would like optimize. \section{LeNet} Having introduced the building components of CNNs, we now introduce the architecture of LeNet. \begin{table} \centering \begin{tabular}{| l | l |} \hline Layer Type & Configuration \\ \hline Input & size: $28 \times 28 \times 1$ \\ \hline Convolution & $k=5, s=1, p=0, n=20$ \\ \hline Pooling & MAX, $k=2, s=2, p=0$ \\ \hline Convolution & $k=5, s=1, p=0, n=50$ \\ \hline Pooling & MAX, $k=2, s=2, p=0$ \\ \hline IP & $n=500$ \\ \hline ReLU & \\ \hline Loss & \\ \hline \end{tabular} \caption{Architecture of LeNet} \label{tab:lenet} \end{table} The architecture of LeNet is shown in Table.~\ref{tab:lenet}. The name of the layer type explains itself. LeNet is composed of interleaving of convolution layers and pooling layers, followed by an inner product layer and finally a loss layer. This is the typical structure of CNNs. \section{Implementation} The basic framework of CNN is already finished and you need to help fill some of the empty functions. Here is an overview of all the files provided to you. \begin{itemize} \item \code{mnist\_all.mat} contains all the data set needed in your experiment. \item \code{load\_minst\_all.m} loads all the data set and processes the data set into the format we need. \item \code{testLeNet.m} is the main file which does the training and test. \item \code{conv\_net.m} defines the CNN. It takes the configuration of the network structure (defined in \code{layers}), the parameters of each layer (\code{param}), the input data (\code{data}) and label (\code{labels}) and does feed forward and backward propagation, returns the cost (\code{cp}) and gradient w.r.t all the parameters (\code{param\_grad}). \item \code{conv\_layer\_forward.m} does the convolutional layer feed forward. \item \code{conv\_layer\_backward.m} does the convolutional layer backward propagation. \item \code{get\_lr.m} returns the learning rate of each iteration. \item \code{mrloss.m} implements the forward and backward propagation for the loss layer. It calculates the negative log likelihood cost in forward operation and calculates the gradient w.r.t. input data and parameters in backward propagation. \end{itemize} Also provided are two helper functions: \begin{itemize} \item \code{im2col\_conv.m} returns a list of pixels for each feature window, given an input image and layer details (such as padding, stride and output dimensions). You might need to reshape your input to this function and also reshape its output, so please read the function to get a better understanding of how the values are stored. \item \code{col2im\_conv.m} returns a list of the gradients at each pixel of the input image, given a list of gradients for each pixel for each feature window. You might need to reshape your input to this function and also reshape its output, so please read the function to get a better understanding of how the values are stored. \end{itemize} You need to finish the functions listed below: \begin{itemize} \item \code{relu\_forward.m} does the relu feed forward. \item \code{relu\_backward.m} does the relu backward propagation. \item \code{elu\_forward.m} does the elu feed forward. \item \code{elu\_backward.m} does the elu backward propagation. \item \code{inner\_product\_forward.m} does the inner product layer feed forward. \item \code{inner\_product\_backward.m} does the inner product layer backward propagation. \item \code{pooling\_layer\_forward.m} does the pooling layer feed forward. \item \code{pooling\_layer\_backward.m} does the pooling layer backward propagation. \item \code{sgd\_momentum.m} updates the parameters of the model given the gradients. \item \code{elu\_finite\_difference.m} computes the gradient for the elu layer using the finite difference method. \end{itemize} \subsection{Data structure} We use a special data structure to store the input and output of each layer. Specifically: \begin{itemize} \item \code{output.height} stores the height of feature maps \item \code{output.width} stores the width of feature maps \item \code{output.channel} stores the channel size of feature maps \item \code{output.batch\_size} stores the batch\_size of feature maps \item \code{output.data} stores actual data of feature map. Note here \code{output.data} is a matrix with size \newline $[$\code{height}$\times$\code{width}$\times$\code{channel}, \code{batch\_size}$]$. If necessary, you can reshape it to $[$\code{height}, \code{width}, \code{channel}, \code{batch\_size}$]$ during your computation, but remember to reshape it back to a two dimensional matrix at the end of each function. \item \code{output.diff} stores gradient w.r.t \code{output.data}. This is used in backward propagation. It has the same shape as \code{output.data}. \end{itemize} For each layer, we use \code{param} to store the parameters: \begin{itemize} \item \code{param.w} stores the weight matrix of each layer. \item \code{param.b} stores the bias of each layer. \end{itemize} \noindent Size and structure of some output variables that could be confusing: \begin{itemize} \item \code{param\_grad} has the same shape as \code{param}. \item \code{input\_od} and \code{input\_od\_approx} have the same shape as \code{input.data} \end{itemize} \subsection{Feed Forward} The forward computation in the convolution layer has been implemented for you. \begin{enumerate}[Q1] \setcounter{enumi}{1} \item {\bf [20 points]} Pooling layer: You need to implement the \code{pooling\_layer\_forward.m} function. You can assume the padding is $0$ here. \textbf{Hint:} You might be able to use \code{im2col\_conv.m} and/or \code{col2im\_conv.m} here to make implementation easier. \item {\bf [3 points]} ReLU layer: You need to implement \code{relu\_forward.m} function. The function interfaces are explained in the code. \item {\bf [10 points]} Inner product layer: You need to implement \code{inner\_product\_forward.m} function. \end{enumerate} \subsection{Backward Propagation} Let us assume layer $i$ computes a function $f_{i}$ with parameters $w_{i}$, then the final loss is computed as: \begin{equation} l = f_{I}(w_{I}, f_{I-1}(w_{I-1}, ...)). \end{equation} We want to optimize $l$ over the parameters of each layer. We can use chain rule to get the gradient of the loss w.r.t the parameters of each layer. Let the output of each layer be $h_{i} = f_{i}(w_{i}, h_{i-1})$. Then the gradient w.r.t $w_{i}$ is given by: \begin{align} \frac{\partial l}{\partial w_{i}} = & \frac{\partial l}{\partial h_{i}} \frac{\partial h_{i}}{\partial w_{i}}, \\ \frac{\partial l}{\partial h_{i-1}} = & \frac{\partial l}{\partial h_{i}} \frac{\partial h_{i}}{\partial h_{i-1}}. \end{align} That is, in the backward propagation, you are given the gradient $\frac{\partial l}{\partial h_{i}}$ w.r.t the output $h_{i}$ (stored in \code{output.diff}) and you need to compute gradient $\frac{\partial l}{\partial w_{i}}$ w.r.t the parameter $w_{i}$ (\code{param\_grad.w} and \code{param\_grad.b}) in this layer (ReLU layers and pooling layer do not have parameters , so you can skip this step), and the gradient $\frac{\partial l}{\partial h_{i-1}}$ w.r.t the input (\code{input\_od}) (which will be passed to the lower layer). The backpropagation for the convolution layer, \code{conv\_layer\_backward.m} has been implemented for you. \begin{enumerate}[Q1] \setcounter{enumi}{4} \item {\bf [20 points]} Pooling layer: You need to implement the \code{pooling\_backward.m} function for max pooling. \textbf{Hint:} You might be able to use \code{im2col\_conv.m} and/or \code{col2im\_conv.m} here to make implementation easier. \item {\bf [3 points]} ReLU layer: You need to implement the \code{relu\_backward.m} function. \item {\bf [10 points]} Inner product layer: You need to implement the \code{inner\_product\_layer\_backward.m} function. \end{enumerate} \subsection{Training and SGD} Having completed all the forward and backward functions, we can compose them to train a model. \code{testLeNet.m} is the main file for you to specify a network structure and train a model. \subsubsection{Network Structure} The function modules are written so that you can change the structure of the network without changing the code. At the head of \code{testLeNet.m}, we define the structure of LeNet. It is consisted of the 8 layers, the configuration of layer \code{i} is specified in \code{layers\{i\}}. Each layer has a parameter called \code{layers\{i\}.type}, which define the type of layer. The configuration of each layer is clearly explained in the comment. After defining the layers, we use \code{init\_convnet.m} to initialize the parameters of each layer. The parameters of layer \code{i} is \code{param\{i\}}, \code{param\{i\}.w} is the weight matrix and \code{param\{i\}.b} is the bias. \code{init\_convnet.m} will figure out the shapes of all parameters and give them an initial value according to the layer configuration \code{layers}. We use uniform random variables within given ranges to initialize the parameters. You can refer to \code{init\_convnet.m} for further details. \subsection{SGD} After the network structure is defined and parameters are initialized, we can start to train the model. We use stochastic gradient descent (SGD) to train the model. At every iteration, we take a random mini batch of the training data and call \code{conv\_net.m} to get the gradient of the parameters, and we then update the parameter based on the gradients (\code{param\_grad}). We use stochastic gradient with momentum to update the parameters: \begin{align} \theta =& \mu\theta + \alpha \frac{\partial l}{\partial w}, \\ w = & w - \theta, \end{align} where $\theta$ accumulates the gradients over the history, the momentum $\mu$ determines how the gradients from previous steps contribute to current update and $\alpha$ is the learning rate at current step. See the UFLDL tutorial \footnote{\url{http://ufldl.stanford.edu/tutorial/supervised/OptimizationStochasticGradientDescent/}} for a detailed explanation of momentum. The learning rate $\alpha$ is a sensitive parameter in neural network models. We need to decrease the learning rate as we iterate over the batches. Here we choose the following policy to decrease the learning rate: \begin{equation} \alpha_{t} = \frac{\epsilon}{(1 + \gamma t)^{p}}, \end{equation} where $\epsilon$ is the initial learning rate, $t$ is the iteration number, and $\gamma$ and $p$ controls how the learning rate decreases. This part is already implemented for you in \code{get\_lr.m}. We impose L2 regularization (or weight decay) on our weights parameters (\code{param.w}), so the loss becomes \begin{equation} l_{reg} = l + \frac{\lambda}{2}\sum_{i}w_{i}^{2} \end{equation} and the gradient w.r.t $w_{i}$ becomes: \begin{equation} \frac{\partial l_{reg}}{\partial w_{i}} = \frac{\partial l}{\partial w_{i}} + \lambda w_{i} \end{equation} \begin{enumerate}[Q1] \setcounter{enumi}{7} \item {\bf [7 points]} You need to implement \code{sgd\_momentum.m} to perform sgd with momentum. \code{param\_winc} is provided to store the history accumulative gradient ($\theta$ here). Note that you need to update both $w$ and $b$ in each \code{param} structure. \end{enumerate} After finishing all the above components, you can run \code{testLeNet.m} and get the output like this \begin{verbatim} cost = 0.490166 training_percent = 0.828125 cost = 0.120790 training_percent = 0.984375 cost = 0.065535 training_percent = 1.000000 test accuracy: 0.962400 cost = 0.186757 training_percent = 0.921875 cost = 0.052646 training_percent = 0.984375 cost = 0.018671 training_percent = 1.000000 test accuracy: 0.974500 \end{verbatim} Within each training epoch, you will see the training loss after processing a portion of the training data and at the end of the epoch, you will see the test accuracy. We can see the training cost is generally decreasing. Note that \code{testLenet.m} loads only a subset of the MNIST data by default. In case you're curious, you can run the code with the whole dataset by flipping \code{fullset} to \code{true}. After the training is finished, the test accuracy you should get with the full set is about 99.1\%. You can find out the state of the art results on this problem online \footnote{\url{http://rodrigob.github.io/are_we_there_yet/build/classification_datasets_results.html}}. It takes several hours to finish training. The actual training time depends on the computer you use and your implementation. \section{Feature Visualization} After you finish training, you can take the model and visualize the internal features of the LeNet. Suppose we want to visualize the output of the first four layers of the data point \code{xtest(:, 1)} (i.e., the first image of test set). Refer to \code{vis\_data.m} on how to do show an image. The output of first layer is simply the image itself (because the first layer is data layer). The output of the second layer (convolution) is $20$ images, each of size $24 \times 24$, hence $24 \times 24 \times 20$, and similarly, the output of the third layer (max pooling) is of size $12 \times 12 \times 20$, and so on. \begin{enumerate}[Q1] \setcounter{enumi}{8} \item {\bf [5 points]} Visualize the output of the second and third layers. Show $20$ images from each layer on a single figure file (use \code{subplot} and organize them in $4\times 5$ format). \item \begin{enumerate} \item {\bf [1 points]} Compare the output of the second layer and the original image (output of the first layer), what changes do you find? \item {\bf [1 points]} Compare the output of the third layer and the output of the second layer, what changes do you find? \item {\bf [3 points]} Explain your observation. \end{enumerate} \end{enumerate} Submit your plots and explanation on Gradescope. \section{Improving LeNet} We now have the complete implementation of LeNet. We will now try to improve it by using a trick that has been recently proposed. Exponential Linear Units (ELU) have been shown \cite{clevert2015fast} to work better than ReLU when the network is sufficiently deep. This is the ELU function \begin{equation} \text{elu}(x) = \begin{cases} x & x > 0\\ \alpha(e^{x} - 1) & x \leq 0 \end{cases} \end{equation} \subsection{Implement ELU} \begin{enumerate}[Q1] \setcounter{enumi}{10} \item \textbf{[5 points]} Implement \code{elu\_forward.m}. Set the value of $\alpha = 1.0$. \item \textbf{[5 points]} Implement \code{elu\_backward.m}. \item \textbf{[2 points]} Rerun \code{testLeNet.m} with ELU activation and report the test accuracy. Is this better or worse than the accuracy with ReLU? \end{enumerate} \subsection{Extra Credit: Debugging gradients} One way to check whether your implementation of analytical gradients is correct is to compare the gradient values against the approximation given by finite difference. Recall that the derivative of a function is defined as follows. \begin{equation} f^{'}(x) = \lim_{h \to 0} \frac{f(x + h) - f(x)}{h} \end{equation} You can use this expression to approximate $f^{'}(x)$ by computing the quantity of the fraction above with a small value of $h$. \begin{enumerate}[Q1] \setcounter{enumi}{13} \item \textbf{[5 points]} Implement finite difference to check gradients implemented for ELU. You will have to complete the file \code{elu\_finite\_difference.m}. The inputs are \code{output}, \code{input} and \code{h}, where \code{input} and \code{output} are layer structures, and \code{h} is the small value shown in the expression above. \textbf{Hint:} You'll have to make a call to \code{elu\_forward.m} for this function. Also note that while the gradient being approximated is that of ELU, the returned value must be the gradient of the loss function (i.e., don't forget to perform back propagation). \end{enumerate} \section{Submission Instructions} Below are the files you need to submit: \begin{itemize} \item \code{relu\_forward.m} \item \code{relu\_backward.m} \item \code{elu\_forward.m} \item \code{elu\_backward.m} \item \code{inner\_product\_forward.m} \item \code{inner\_product\_backward.m} \item \code{pooling\_layer\_forward.m} \item \code{pooling\_layer\_backwawrd.m} \item \code{sgd\_momentum.m} \item Optionally \code{elu\_finite\_difference.m} \end{itemize} Please put these files in a folder called \code{hw6} and run the following command: \code{\$ tar cvf hw6.tar hw6} \noindent Submit the tar file generated. Ensure that all the required files are present even if unimplemented and that you are able to see a total score on Autolab. \bibliographystyle{abbrv} \bibliography{bibliography} \end{document}