\documentclass[11pt]{article} \usepackage{fullpage} \begin{document} \begin{center} \Huge\bf Homework \#\,\,3\\ \Large\bf 15-486/782: Artificial Neural Networks\\ \large\bf Exercise created by Dean Pomerleau and Dave Touretzky\\[.2in] \end{center} \noindent {\bf Due Wednesday, September 27.} This homework examines the use of the backpropagation learning rule on the difficult real world task of autonomous road following. You will train and test an MLP that maps simulated road images to the correct steering direction for that image, and examine the representations the network develops. Make sure you've done all the readings relevant to backpropagation learning and the ALVINN system before beginning this assignment. {\bf Answer all questions appearing in the text. Hand in plots where requested. You do not need to hand in any color figures of weights. If your plots are not in color, then use different line types (solid, dashed, dotted) for multiple curves on the same plot.} \begin{enumerate} \item First we'll take a look at the datasets for this problem. Use the \verb+load+ command to load the file \verb+alvinn_data.mat+ from the \verb+matlab/alvinn+ class directory. (Note that this is a binary file, so if you FTP it to another computer, be sure to use binary mode for the file transfer.) Use the \verb+whos+ command to see the variables that were loaded. The training set consists of the variables \verb+Patterns+ (250 actual road images taken from the Navlab's camera, each $30\times 32$ pixels, encoded as a 960 element vector), \verb+Desired+ (250 desired output vectors, each consisting of 30 elements, depicting a gaussian bump centered on the correct steering direction), and \verb+Positions+, a vector of 250 values giving the correct steering direction for each road image as a real number between 1 and 30. There are other variables as well, which will be explained later. Also included in the \verb+alvinn+ directory are some Matlab routines you will want to copy. To ``take a tour'' through the training data, type: \verb+tour(Patterns,0,Desired)+. You can stop the tour by hitting \verb+^C+. Note that the window displaying the road images has two buttons marked ``$+$'' and ``$-$'' in the top right corner; these can be used at any time to scroll through the road images. There is also a ``cross-validation'' dataset (actually just a test set, since we won't be doing true cross-validation in this problem) which we'll use to determine when to stop training the network. Take a tour through this dataset by typing \verb+tour(CVPatterns,0,CVDesired)+. Questions: What kind of road is used in the training and cross validation datasets? What prominent road feature does the cross-validation dataset contain that is almost entirely absent from the training dataset? \item Now we will assemble the core routines for training the backprop network. Start with the Matlab scripts \verb+approx+, \verb+approxhelper+, and \verb+bp_innerloop+ in the class \verb+matlab/bp+ directory. Copy the scripts to your directory and rename the first two to \verb+alvinn+ and \verb+alvinnhelper+. \begin{enumerate} \item Modify your \verb+alvinn+ routine to make it a script rather than a function. Fix the number of hidden units at 4. Set \verb+DerivIncr+ to 0.1 and \verb+Momentum+ to 0.9. \item The \verb+alvinn+ script sets up a ``learning rate schedule'' for backprop, which is then used by \verb+alvinnhelper+. When training large networks, it is advantageous to start off with a slow learning rate for the first 50 or so epochs so the hidden units can sort themselves out and get moving in the right direction before taking any large steps in weight space. Then the learning rate can be safely increased. It may help to reduce the learning rate later in training to fine tune the weights. For the ALVINN problem, set your learning rate schedule to run for 50 epochs at 0.001, then 100 epochs at 0.007, and finally 50 epochs at 0.004. \item Another trick to provide better initial conditions for backprop learning is to make sure the magnitudes of the initial random weights are small enough that the hidden units are not driven to the flat spots on the sigmoid, yet large enough that the units are effectively differentiated. For large networks such as ALVINN, a unit's initial random weights should be scaled by (i.e., divided by) the square root of the fan-in. Make this change to your \verb+alvinn+ routine. \item As we saw in class, a unit's learning rate should also be scaled by its fan-in. Make this change to the \verb+bp_innerloop+ script. \item Because we will be comparing performance of the network on datasets of different sizes, we should normalize the total sum-squared-error (called {}\verb+TSS+) by dividing by the number of patterns. Modify the \verb+bp_innerloop+ script to do this. \item Another common backprop trick is called ``weight decay''. At each time step, after the weights are updated, the magnitudes of all weights are reduced a tiny amount by multiplying by a constant slightly less than one. With repeated reductions, the weights of ``unimportant'' connections will decay to zero, while for the important connections, i.e., the ones that contribute significantly to solving the problem, the learning algorithm will cause the weights to grow, counteracting the decay effect. Modify \verb+bp_innerlooop+ to multiply the newly computed weights by \verb+(1-WeightDecay)+. Typical values for this parameter range from 0 (for no decay) up to 0.05. \item Modify \verb+alvinnhelper+ to display its progress during learning, as follows. On every iteration it should print the epoch number and the TSS error. On every fifth iteration, it should select figure 1 and call \begin{center} \verb+PlotAlvinn(epoch,Patterns,Result2,Desired)+ \end{center} \noindent and select figure 2 and call \verb+PlotAlvinnWeights(Weights1,Weights2)+. \item Now you are ready to try training an ALVINN network. Watch the hidden unit weights as the network learns. What effect does the weight decay parameter have on learning? \end{enumerate} \item A network trained to minimum sum-squared error on the training set may not produce the best possible results on a new test set. The reason is that in a net with many parameters and a modest sized training set, overfitting can occur. With overfitting the network learns weights reflecting not just the function we intended it to learn, but also any statistical irregularities (noise) in the training set. The specific peculiarities of the training set will not exist in the test set (which of course has peculiarities of its own), so the network does not do as well as it could if it had not tried to model the training set noise. Therefore, we use performance on a second dataset, the cross-validation dataset, to determine when to stop training. Generally, the training set error will continue to decrease as training progresses, but the cross-validation error will decrease to some minimum value and then begin to increase. Note: although the network is always trying to move downhill on the error surface, if the learning rate is set to an aggressive (high) value, the sum-squared error on the {\it training} set can increase on some trials, when the network takes too big a step in weight space. It will eventually go down again. {\bf If the error does not get down to around 2.0, the network has not really learned this dataset; there may be something wrong with your initial weights, fan-in correction, or learning schedule.} \begin{enumerate} \item Modify \verb+alvinn+ to create \verb+CVInputs1+ from \verb+CVPatterns+, just as \verb+Inputs1+ was created from \verb+Patterns+. \item Write a function \verb+forwprop+ that peforms just the feed-forward computation part of an MLP network. You can extract this code from \verb+bp_innerloop+. Your function should take the following form: \begin{center} \verb+[Result1,Result2,TSS] = forwprop(Inputs1,Desired,Weights1,Weights2)+ \end{center} Note that since \verb+forwprop+ is a function, variables such as \verb+Result2+ and \verb+TSS+ are local to it, and do not conflict with the global variables of the same name used by your \verb+alvinn+ script. \item Modify \verb+alvinnhelper+ to run a forward propagation step on the cross-validation dataset with each epoch of training, storing the return values in variables \verb+CVResult1+, \verb+CVResult2+, and \verb+CVTSS+. \item Modify \verb+alvinnhelper+ to record the \verb+TSS+ and \verb+CVTSS+ values for each epoch in an array. It should also keep track of the best weights seen so far for each case, i.e., if the current weights produce the lowest \verb+TSS+ value seen so far then set \verb+Best_Weights = {Weights1 Weights2}+. (The brace notation is a ``cell array''; see the Matlab manual for an explanation.) Store the best weights seen so far on the cross-validation set in the variable \verb+Best_CV_Weights+. \item Modify \verb+alvinnhelper+ to print the cross-validation error as well as the training error for each epoch. It should also graphically display the record of both error measures, as follows. On every fifth epoch, in addition to displaying the network output in figure 1 and the current weights in figure 2, select figure 3 and plot the complete history (so far) of \verb+TSS+ and \verb+CVTSS+, using lines of different colors. In addition, plot an open circle symbol of the appropriate color at the location of the lowest value for each line. Graphics hints: use \verb+hold on+ so you can plot multiple things in the same figure. Use \verb+axis([0 200 0 25])+ to fix ths ranges of the graph so it doesn't get rescaled each time you add new points. Use \verb+legend+ to label the lines of the graph. \item Compare the weight vector that gives the best generalization on the cross-validation set with the weight vector that gives the lowest error on the training set. Describe in a sentence or two how they differ. You can plot the best cross-validation weight vector by typing: \verb+PlotAlvinnWeights(Best_CV_Weights{1},Best_CV_Weights{2})+. \item For the rest of this exercise we will want to stick with the weights that give the best generalization on novel inputs, so use \verb+forwprop+ with the best CV weights to find the network's best output on the cross-validation set. \end{enumerate} \item If we want to use our neural net to drive a car, we must extract a single steering direction value from the network's output. \begin{enumerate} \item Write a function \verb+[dir,err]=extractdir(Result,Gaussians)+ that takes as input a 30 element vector (could be one column of \verb+Result2+ or \verb+CVResult2+) and a set of model gaussians, and returns two numbers: a number \verb+dir+ between 1 and 30 indicating the steering direction, and the sum-squared error \verb+err+ between the result vector and the best-matching gaussian. Here's how to compute the answer. The global variable \verb+Gaussians+ from the \verb+alvinn_data+ file is a $30\times 291$ matrix containing 291 gaussian bumps with peaks at locations 1 to 30 in steps of 0.1. Given a vector of output unit values, compute the sum-squared distance between that vector and each of the 291 gaussians. If $i$ is the index of the minimum-distance gaussian, then the corresponding steering direction is $1+(i-1)/10$. As a test: \verb+[dir,err]=extractdir(Desired(:,1),Gaussians)+ should return a steering direction of 12.6 and a sum-squared error of 0.0037. Note that \verb+Positions(1)+ equals 12.6610. \item The correct steering direction for each pattern is given in the variable \verb+Positions+ or \verb+CVPositions+. Write a function \verb+cmpbump(imageno,result,Gaussians)+ that takes a road image number, a matrix of output patterns such as \verb+CVResult2+, and a set of model gaussians as inputs, and plots both the actual output pattern for that road image and the curve of the best-matching gaussian. Find an image for which the match is very close, and an image for which the match is poor. Hand in plots for both images. \end{enumerate} \item An extremely important function that any MLP applied to a real world problem must address is confidence estimation. The network needs to be able to determine when it is confused, to avoid making catastrophic mistakes (e.g., steering into a ditch when it comes to a confusing stretch of roadway). One approach thats allows the network to estimate its own confidence is a simple extension to the gaussian matching technique you implemented above. This approach is called Output Appearance Reliability Estimation (OARE). OARE is based on the premise that if the network is trained to output a gaussian peak of activation with a particular shape, and the network's actual output doesn't have this shape (either because there are multiple peaks in the output, or no strong peak at all), then the input pattern probably depicts a situation unlike anything in the training set, and the network's response is likely to be incorrect. \begin{enumerate} \item Use the cross-validation images for this task. For each cross-validation pattern, find the best matching gaussian output vector and the sum squared error of the match using the \verb+extractdir+ procedure from the previous question. This sum squared difference is called the output appearance error. The lower the output appearance error, the more closely the shape of the network's output matches the ideal gaussian shape, and the more confident the network should be of its output. Normalize the vector of output appearance errors on the set of cross-validation patterns by dividing by the maximum value. \item For each cross-validation pattern, compute the steering error as the square of the difference between the estimated steering direction (as returned by \verb+extractdir+) and the correct direction given in \verb+CVPositions+. Normalize the vector of steering errors by dividing by the maximum value. \item Write a function \verb+PlotOARE(result,positions,Gaussians)+ that plots the OARE and squared steering error values for a set of output patterns. \item If your network has been trained properly, you should see three regions containing peaks in the OARE error for the cross validation dataset. Two of these regions have corresponding peaks in the steering error. Thus, OARE seems to be a fairly good predictor of steering error. Question: what is happening in the road images where these two peaks occur? \end{enumerate} \item A {\it sensitivity analysis} of ALVINN's hidden units helps to reveal how they respond to roads at different shifts and orientations. In this portion of the exercise you will conduct a simplified sensitivity analysis of your trained network, looking only at shifts. \begin{enumerate} \item Write a function to construct a simulated $30\times 32$ road image with a trapezoidal shape. The road should be 10 pixels wide at the top of the image and 24 pixels wide at the bottom. Road pixels should have values of $0.6$, and non-road pixels should have values of $-0.6$. \item Write a function to generate a set of road images shifted left or right of center by varying amounts. (Since we're looking only at shifts, not rotations, this is trivial to compute.) At the furthest left or right shift, no road is visible. At intermediate values of shift, only part of the road may be visible. Plot two of your simulated road images with different shift values and hand them in as part of your answer to this problem. \item Use your \verb+forwprop+ function to run the trained network on your sequence of synthetic road images. The return value \verb+Result1+ holds the hidden unit activations. Plot the hidden unit activation as a function of road shift; use a different color line for each hidden unit. (Note: the \verb+plot+ function can plot multiple lines at the same time if given a matrix argument, and each line will automatically be assigned a different color. Or you can specify colors explicitly if you prefer) Use \verb+legend+ to label your lines with the corresponding hidden unit number. \item What correlation do you see between the locations of peaks and valleys in the sensitivity plot and the positive and negative values of the hidden-to-output weights? (Give a qualitative description; you don't need to compute correlation coefficients.) \end{enumerate} \item How well does your trained network handle multi-lane roads? Try running it on the images in \verb+TwoLanePatterns+. What is your assessment of its performance? \end{enumerate} \noindent {\bf Hand in the following on September 27:} \begin{itemize} \item all the code you wrote \item a printout of a sample training run showing the training set error and CV error for each epoch \item the plots you generated \item short answers to the various questions asked in the text above. \end{itemize} \end{document}