\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}
