OverviewLanguage and OSPerceptronBackpropagationAssignmentPerceptronBackpropagationSubmission DetailsCPSC 420-500: Program 3, Perceptron andBackpropagationYoonsuck ChoeDepartment of Computer ScienceTexas A&M UniversityOctober 31, 20081 OverviewYou will implement perceptron learning from scratch (see section 3 for details), andtrain it on AND, OR, and XOR functions. Then, you will take an existing backprop-agation code (see section 4), train it and test it under different conditions and reportyour findings. The same three boolean functions will be used for the backpropagationlearning. For further details on perceptrons and backpropagation, see the lecture slidesand also Hertz et al. (1991). Specific submission instruction will be given in section 5and section 6.2 Language and OSYou may use either C/C++, Java, Matlab (or Octave), or Lisp. The resulting codeshould be able to compile and run on the departmental unix host (unix.cs.tamu.edu).You may use a different language with a permission from the instructor, in which caseyou will be asked to do a demo in front of the TA.To compile your programs other than Lisp (which you already know), see the followinginstructions.• C program file: perceptron.cto compile: cc -o perceptron perceptron.c -lmto execute: ./perceptron• C++ program file: perceptron.Cto compile: c++ -o perceptron perceptron.C -lmto execute: ./perceptron1• Java program file: perceptron.javato compile: javac perceptron.javato execute: java perceptronThe full paths for the compilers are (on compute.cs.tamu.edu):• /usr/bin/cc• /opt/csw/gcc3/bin/g++• /usr/jdk/latest/bin/java• /usr/jdk/latest/bin/javac3 PerceptronPerceptron activation is defined as:Output = step 2Xi=0W [i] ∗ INP [i]!, (1)where step(X) = 1 if X ≥ 0 and step(X) = 0 if X < 0 (see figure 1).W[2]W[1]W[0]−1 X Yf(X,Y)INP[0] INP[1] INP[2]Figure 1: Perceptron. The input INP [0] is the bias unit, fixed to −1, and has an associatedweight W [0], which is the threshold. The two inputs X and Y are given and the output f (X, Y )will be calculating (or attempting to calculate) a boolean function, one of OR, AND, or XOR.Implement a perceptron with two input units (three, including the bias unit that has afixed input value -1) and one output unit. Your program should take three inputs fromthe command line.1. maximum number of epochs to run (integer),2. learning rate parameter α value (double),3. function selection string (“and”, “or”, and “xor”).2For example, a typical run would go like this ($ is the unix prompt):$ ./perceptron 10000 0.0001 andA pseudo code for perceptron learning is as follows:1. Initialize weights to random numbers between 0.0 and 1.0. Note that you havejust one set of 3 weights (W [0], W [1], W [2]). You will train this same set usingthe four input-target pairs.2. Initialize epoch count to 0.3. while sum of (target − output)2for all input patterns is not 0 do:• for each input-target pattern(a) present input and calculate output(b) calculate the error = target − output(c) update the weights W [i] using the perceptron learning rule.• endfor• increment epoch count• if (epoch count > max epochs), break from while loop4. Print out the output for the inputs (0,0), (0,1), (1,0), and (1,1).4 BackpropagationFor backpropagation, you will download the following file (make it one line):http://faculty.cs.tamu.edu/choe/src/backprop-1.6.tar.gzand run it under different conditions. First, you need to unzip and untar it by runningthe following:$ tar xzvf backprop-1.6.tar.gz$ cd backpropthen read the README file to learn how to compile and run it.Running the bp program (which is generated by compiling) will give you a huge dumpon the screen. To selectively view the data you’re more interested in, use the grepcommand. For example, to view the progression of error:3$ ./bp conf/xor.conf | grep ERRand to view the actual output values for the inputs:$ ./bp conf/xor.conf | grep OUT5 AssignmentThis section will detail what you actually have to do and have to submit. All projectsshould be turned in using the csnet turnin.5.1 PerceptronImplement perceptron learning algorithm as detailed in section 3, and with the programconduct the following experiments, and submit the required material, along with thecode and the README file as usual.Experiments:1. Test AND, OR, and XOR for learning rates α = 0.001, and 0.0001. For eachBoolean function, run the experiment with different initial random weights (usethe random number generator function to do this) two times. Discard all runsthat ended in 1 epoch (you will see several of these: why would they occur?).The total number of trial will thus be 2 learning rates × 2 random initial weights× 3 functions to learn = 12. Set the max epoch to 10000 for all trials.2. For each trial, report the following in the README file:(a) initial weights, and show the plot of the decision boundary (the straight linedefined by the weights).(b) final weights, and show the plot of the decision boundary.(c) number of epochs taken to complete training if successful (let us call thisn), and(d) for each epoch, the sum of squared error for all four input patterns.3. Answer these questions in the README file:(a) Do you think perceptron will be able to learn the boolean function f (X, Y ) =¬(X ∨ Y )? What do you think is the role of the sign of the weights in thiscase? Think about the geometric interpretation in that case.4Table 1: Boolean Function f (X, Y ) = ¬(X ∨ Y ).X Y ¬(X ∨ Y )0 0 10 1 01 0 01 1 05.2 BackpropagationWith the provided code, conduct experiments on AND, OR, and XOR. Note that inthe bp.cc code, learning rate α is a named eta, just in case you want to take a lookinside the code.Experiments:1. Test AND, OR, and XOR for learning rates α = 0.01 and 0.001, and plot thesum of squared error for each trial (a total of 6 trials). A total of 3 set of plots(for AND, OR, and XOR), with each set containing 2 curves (for two α’s) is re-quired. Save the plots in image files and name them and1.jpg, and2.jpg,or1.jpg, or2.jpg, xor1.jpg, xor1.jpg .... Use grep to ex-tract the error values (see below), and load that file (dump.txt) in a spread-sheet.$ ./bp conf/xor.conf | grep ERR > dump.txt2. With learning rate α = 0.01, test AND, OR, and XOR, with 1, 2, and 4 hid-den units, Plot the sum of squared error for each trial. A total of 3 set of plots(for AND, OR, and XOR), with each set containing 3 curves (for three differentnumber of hidden units) is required.