********************************************************************** File ~/../public/A5/README Homework Assignment 5 CSE 150, UCSD Fall 2002 Due: Saturday, december 7, Midnight ********************************************************************** >>> SUMMARY: This programming assignment is to implement a back propagation learning system. Please be aware that the algorithm given in the figure in the book is incorrect, although the verbal description below it is not. The goals of this assignment are for you to: (1) Create a running version of a two layer sigmoidal neural network; (2) Implement the backpropagation learning procedure for setting the weights based on a file of training patterns; (3) Experiment with the ability of the network to learn different types of functions of the inputs. Requirements for your simulator: 1. It should be able to read in a file of patterns. The format of the pattern file is: Npatterns input_size output_size ipattern1 opattern1 ipattern2 opattern2 ... ipatternN opatternN The network will configure itself based on the pattern length and the hidden layer size. Note that the hidden layer size is not given above. This should be a parameter to your program. This parameter is thus *required*. 2. The simulator should allow you to train the network for a specified number of epochs, or until convergence. During this process, the system should print out the root mean squared error after every pass through the patterns (one epoch), as in the following example : epoch 1 : RMSE = 1.07067 epoch 2 : RMSE = 1.06953 epoch 3 : RMSE = 1.06878 epoch 4 : RMSE = 1.06833 epoch 5 : RMSE = 1.06808 The root mean squared error is an error measure based on the sum squared error, except that it does not vary with the number of patterns in the training set. It also enjoys the property that if your network has just learned the average teaching signal (ignoring the input altogether), it is 1.0, and if your network has learned the patterns perfectly, it is 0.0. Here it is: SUM(over all pats (p)) SUM(over all outputs (i)) (Teacher_pi - output_pi)^2 RMSE = ----------------------------------------------------------- SUM(over all pats (p)) SUM(over all outputs (i)) (Teacher_pi - avg_Teacher_i)^2 Where the notation X_ij means X[i][j], Teacher_pi means Teacher[p][i] and avg_Teacher_i = [SUM(over all pats (p)) Teacher_pi]/NPATS So the denominator above is constant, and can be computed by a couple of passes through the training set, once to get the average, then a second time to get the sum. Example: pats: 1 2 3 4 5 6 7 8 avg_teacher --------------------------------------------------- teacher for output 1: 1 1 1 1 0 0 0 0 0.50 teacher for output 2: 1 1 1 1 1 1 0 0 0.75 RMSE Denominator for above example : 4 * (1 - .50)^2 + 4 * (0 - .50)^2 + 6 * (1 - .75)^2 + 2 * (0 - .75)^2 = 3.5 Note that calculating RMSE requires finding the error (i.e., Teacher_pi - output_pi) for all output units for all patterns, and that you will get different results for RMSE depending on whether you take output_pi to be the output before or after weights are changed via training during the epoch. For consistency, we ask that you use the output_pi values for each pattern *before* the weights are changed in your RMSE computation (this should also make things a bit more efficient). 3. Your simulator should give you a way of saving weights and reading them back in, and observing the behavior of the network with those weights. You should save, along with the weights, the size of the input, HIDDEN, and output, so that your simulator should be able to check whether a set of weights makes sense when given a pattern file. To make sure we can share weights as well, the format of the weight file should be (in ASCII): input_size hidden_size output_size bias[1..hidden+output_size] input->hidden weight_matrix row 0 input->hidden weight matrix row 1 ... input->hidden weight matrix row hidden_size - 1 hidden->output weight_matrix row 0 hidden->output weight matrix row 1 ... hidden->output weight matrix row output_size - 1 When printing in ascii format, use a floating point format equivalent to that obtained with the C "%g" format specifier, so that precision is not lost. 4. Finally, you should demonstrate empirically that it can learn AND, OR, NOT, XOR and TC. Implementation Notes As described in class, you will need variables to hold the output vector, the two weight matrices W1 (which should have hidden_size rows and input_size columns, that is, the weight FROM input i TO hidden unit j is W1[j][i]), and W2 (which should have output_size rows and hidden_size columns, that is, the weight FROM hidden i TO output unit j is W2[j][i]), the input pattern matrix and the teaching pattern matrix. The input pattern matrix will be of dimension Npatterns by input_size, and the teaching pattern matrix will be of dimension Npatterns by output_size. You don't need a separate input vector because it is just given by one row of the input pattern matrix. Similarly, you don't need a separate teaching vector, as it is given by one row of the teaching pattern matrix. Below, I will use "teacher[i]" to refer to the ith component of one row of the teaching pattern matrix; that is, teacher[pattern_number][i]. This is because we are only considering one pattern at a time, so this should not be confusing. The same convention is also used below for "input[i]". As with the perceptron network, we will use a separate bias for every processing unit. This now means that there is a bias for every hidden unit as well as for every output unit. Just as before, the bias is ADDED into the net input of a unit. This means you now need a vector called "bias" of size HIDDEN_SIZE + output_size. (Or, you could have two vectors if that is easier for you.) Again, as with perceptrons, training a BP network involves cycling repeatedly (once for each pattern) through two phases: a phase propagating activation forward through the network to compute the unit activations, and then a phase changing the weights to make the network more correct. Unlike perceptrons, however, backpropagation requires an extra step in the weight change phase in order to backpropagate error. In this error backpropagation step, we must compute "deltas" as a measure of the incorrectness of each hidden and output unit. To propagate activation forward through the network, you first propagate activation from the inputs to the hiddens, and then propagate activation from the hiddens to the outputs. To propagate activation between the inputs and hiddens, you first compute the net input to each hidden unit, and then apply the activation function (given below) to compute the activation of each hidden unit. Once all of the hidden unit activations have been computed in this manner, they are then used to propagate activation to the outputs. As with input to hidden activation propagation, hidden to output activation propagation proceeds by first computing the net input to each output unit, and then computing the activation of each output unit (again, using the activation formula given below). The net input to each unit is the weighted sum of its inputs plus its bias. Hidden units receive input from the input units, and the weights to hidden unit i are given by row i of the W1 weight matrix. Output units receive input from the hidden units, and the weights to output unit i are given by row i of the W2 weight matrix. The activation function for all hidden and output units is the sigmoidal activation function. Thus, the activation of hidden or output unit i is given by the following formula, where net[i] is the net input to unit i, and exp(n) is the exponential function e^n : activation[i] = 1/(1 + exp(-net[i])); Once activation has been propagated forward through all layers of units in the network, we can then perform error backpropagation to change the weights so the network will learn. This entails computing deltas for each of the output units and hidden units. First, you compute the delta for the outputs as: delta[output i] = (teacher[i] - activation[i])*activation[i]*(1-activation[i]) the last two terms corresponding to the slope of the activation function at this point. Then, you propagate the delta's back through the network, computing the delta's of the hidden units as: delta[hidden j] = {SUM(over i) W2[i][j]*delta[i]} * activation[j]*(1-activation[j]) Ok, now we have the delta's for every unit in the network! Now we are ready to change the weights. Since we are going to use MOMENTUM, which speeds up online backpropagation considerably, as explained in class, we need to compute deltas for the weights. Each weight delta is a weighted average of all of the previous weight changes that have been made to its corresponding weight throughout *all* epochs of training. At the beginning of training, each weight delta should be initialized to 0.0. Then, every time before weight W[i][j] is to be changed, the corresponding weight delta, w_delta[i][j] must be updated according to : w_delta[i][j] = (eta * delta[i] * z[j]) + (alpha * w_delta[i][j]); where eta is the learning rate (set as a parameter, default 0.1), delta[i] is the delta for unit i, z[j] is either the activation of a hidden unit (if unit i is an output) or is an input (if i is a hidden unit), and alpha is the momentum parameter (set on the command line as -m, default to 0.9). Having computed the weight delta corresponding to weight W[i][j], we are ready to change the weight. We change weight W[i][j] as follows : W[i][j] = W[i][j] + w_delta[i][j]; Since the network biases are just the weights from units always having an activation of +1.0, we can apply momentum to the biases as well. Hence, analogous to the way we've been storing weight deltas, we'll store a vector of bias deltas. Like the weight deltas, the bias deltas must be initialized to zero once at the beginning of training. Then, at each pattern presentation, we update the bias delta values using the equation : b_delta[i] = (eta * delta[i]) + (alpha * b_delta[i]) Once we have computed the bias deltas, we can update the biases using the rule : bias[i] = bias[i] + b_delta[i]; Notes on Implementing Random Pattern Presentation For some problems, always presenting the patterns in the training set in the same order during training can slow learning and lead to an increase in local minima. To get around this problem, we will add to our simulators some code that causes the order in which patterns are presented for training to be re-randomized on every epoch. In order to implement random pattern presentation, you will need some way of randomly permuting the order in which patterns are chosen for training by your program. To make this easier for you, we will code up a function in matlab that does the following (NOTE: this has not been done yet!): 'next_rand_index' in the file next_rand_index.m. next_rand_index takes two arguments : reset and limit. When the first argument, reset, is set to 1, next_rand_index creates a new random permutation of the integers in the interval [0, limit-1] and sets an internal counter to 0. After having been initialized by a call with reset=1, successive calls to next_rand_index with reset=0 will return the next integer in the permuted sequence and increment next_rand_index's internal counter. Once all of the integers in the permuted sequence have been returned, additional calls to next_rand_index(0, limit) will return -1. As an example of how to use the next_rand_index function (if you were coding this in C!), suppose you have Npatterns in your training set, then next_rand_index(1, Npatterns); /* reset the sequence generator */ while( (i=next_rand_index(0, Npatterns)) >=0 ) { /* train on pattern i */ } will cause all of the patterns to be trained on in some random order. We will provided a variety of sample files in A5/Examples/. >>> ASSIGNMENT SPECIFICATION : To be determined, but at least: What to Turn In + README : A brief (roughly one to two pages) description of your overall approach to the problem - how you organized the solution (e.g., the major functions), any special features you might have added, etc. Also, you must document your bugs! + : all files required to to run your bp network + and.wts : a weight file containing the weights resulting from learning AND with two hidden units + or.wts : a weight file containing the weights resulting from learning OR with two hidden units + not.wts : a weight file containing the weights resulting from learning NOT with one hidden unit + xor.wts : a weight file containing the weights resulting from learning XOR with two hidden unit + tc.wts : a weight file containing the weights resulting from learning the TC problem with any number of hidden units To submit the multiple files required for this assignment, please follow this procedure EXACTLY: 1) create a directory called "hw5", 2) copy ALL and ONLY the files listed above in the 'What to Turn In' section into the "hw5" directory (all of your files should be in "hw5", NOT A SUBDIRECTORY of "hw5" -- be sure your Makefile works with this organization), 3) from the PARENT DIRECTORY of the "hw5" directory, execute the command : tar cvf - hw5 | turnin -c cs150w EXTRA CREDIT: You may obtain extra credit by adding some of the "tricks of the trade" discussed in class, preferably in this order: 1. Use of the "funny tanh" function: Make sure you also use the correct derivative in this case in your weight update code! 2. Initialization of the weights so that they have a standard deviation equal to the fan-in of the unit. 3. normalize the inputs so that each input pattern has 0 mean and unit standard deviation. Also, if using the funny tanh, you would also want the targets to be -1 and 1 if the teaching signal is binary. 4. Actually perform Principal Components Analysis on the input patterns and reduce the dimensionality of them based on the eigenvalues. Matlab has functions built in for this. Only one person did this in the past, and he was already admitted to our PhD program....but that was before we started using matlab! Note that it doesn't help to project your inputs onto ALL of the principal components - you should use the top, say, half of them. These latter two enhancements could be performed outside the simulator by some preprocessing code. Often you want to "eyeball" the eigenvalues to decide where to cut them off.