CS 327: Artificial Intelligence

Assignment 5: Machine Learning

This entire assignment is due on paper in class on Wednesday, Feb. 14. Note that both problems are of equal value, and the second problem requires you to use the computers in the Linux labs (though you will hand in answers on paper).

Genetic Algorithms (10 points)

Genetic algorithms have been proposed as a technique for learning both decision trees and neural networks.

1. Why would one think about using genetic algorithms for these purposes instead of ID3 and backprop? Don't ID3 and/or backprop find the best possible solutions? If not, why would genetic algorithms potentially do better or faster?

2. Decision trees: indicate an appropriate chromosome representation, fitness function, and operators for crossover, mutation, and inversion.

3. Neural networks: indicate an appropriate chromosome representation, fitness function, and operators for crossover, mutation, and inversion.

Neural Networks (10 points)

For this part of the assignment, you will run PDP++, a neural network simulator. This is a "lab" type assignment, which requires you to run PDP from one of the lab Linux machines. There are four questions scattered throughout the exercise, which you should turn in on paper.

source /Accounts/courses/cs327/pdp++/setup

Then to start PDP++ in backprop mode, enter

bp++

After a short time, the bp++> prompt will appear in your command interface window, and a small menubar window will appear somewhere on the screen. This is the PDP++:Root window. You are going to open a pre-defined Project and then run it. To open the project, select .projects / Open In / Root. A file-selector window will appear. In the box at the top, type

/Accounts/courses/cs327/pdp++/demo/bp/xor.proj.gz

After a little time for initialization, the Root menu will move to the right, and you should see two new windows on your screen: A Project window and a window called a NetView. Several other windows will be iconified, we will turn our attention to them in a moment.

The Networks Window

The NetView window (indicated by the word "networks" within the title bar provides us with access to the network that we have created for learning the XOR problem. The NetView window has two sets of menus along with lots of pushbuttons and a display area containing a graphical display of the network.

The NetView itself, the main body of the NetView window, provides a graphical depiction of our network. You can think of the layers of the network arranged vertically, with the units within each layer laid out on a two-dimensional sheet. The input layer is located at the bottom of the netview, with the two input units arranged side by side. In networks with many units per layer the units can be laid out in an X by Y array. The hidden layer is next above the input layer, and we can see the two hidden units, again laid out side by side. The output layer, above the hidden layer, contains just a single unit, aligned to the left of the netview. At present, each unit is displaying its activation, as indicated by the depressed appearance of the act button, together with the yellow highlight. The activation is shown in color in accordance with the color bar shown at the right of the NetView, and by the numeric value printed on it. Either way we see that the activation of all of the units is 0.

The Network has been initialized so that each unit has a random bias weight and so that there are random weights on the connections between the units. We can examine these biases and weights by displaying them on the netview. First, to look at the bias weights, we can click on the bias.wt button. Once we do this, the units will assume colors corresponding to their bias weights. The biases on the input units are not used and can be ignored.

We can also view weights either coming into or going out of a selected unit. The former are called 'receiving weights'. To view the receiving weights of the left hidden unit we first click on the button labeled r.wt. This activates the View button, and turns the cursor into a little hand, indicating that we may now pick a unit to view its receiving weights. We can now click on the left hidden unit, and its receiving or incoming weights are displayed on the units from which they originate; the selected receiving unit is highlighted. We see that this unit receives incoming weights only from the two input units, both somewhat positive. We can proceed to click
on other units to view their incoming weights as well. Note that the input units have no incoming weights. To see the outgoing or 'sending' weights from a unit, we simply click the s.wt button, then click the unit whose sending weights we wish to view. You can verify that the values of the sending weight from the left input unit to the right hidden unit is the same value as the receiving weight to the right hidden unit.

Since all we've done so far is initialize the network's weights there isn't that much else we can look at at this point. However, if we click on the act button, the network will be set to display the activations of units later when we actually start to run the network. Do this now.

***Question 1: Draw the neural network in "standard form", i.e. the way we've been drawing it in class, indicating the weights and biases which you find on the screen. Why would a program such as this represent a network in this fashion, instead of in the way we viewed it in class?

The Environments Window (training data)

A second type of object contained in our Project is the Environment. The environment supplies events (training examples) on request. If we click on the iconified EnviroView window, we can inspect the objects corresponding to each of these Events. The window that pops up displays the names of all four of the events that make up the 'XOR' problem. You can inspect any one of these events by clicking on the appropriate button, and if you do you will see that it consists of two patterns, an input and an output pattern. You can display all four together, by first clicking the left mouse button on the first event button, then clicking the middle mouse button on the other event buttons in order. The color scale indicates the correct interpretation of the colors that indicate the activations of the units. Once you check this out you can go ahead and iconify the EnviroView window again.

***Question 2: Write down the four training points in the order that they appear.

Training and Testing the Network

Rather than starting training right away, let's run through a test before any training is carried out. In the network window, make sure you have "act" selected. Select .processes / ControlPanel / Test in the Project window, then press Step. Now, you will see some action. You will see the activations of all of the units as the first pattern is processed. The input units are both off (0) in the first pattern, and should have the color associated with 0 in the color scale. The hidden and output units all have activations between about 0.4 and 0.6. The same information is displayed in the GridLogView. You should see the epoch number, the Event name, the sum-squared error for this event, and a display showing the activation of the hidden and output units for this event. If you press Step 3 more times you can step through the remaining test patterns. At the end of stepping you should have the results from all four cases visible in the GridLogView.

Now let's run 1 epoch of training. Select .processes / ControlPanel / Train in the Project window, then click on the down arrow next to "n" to change the number of epochs to run at a time to be 1 (instead of 30). Then, click on Step. When you do this, assuming that indeed the act button has been clicked in the NetView, you will see the state of activation in the network change. Click on step again. Keep doing so, and watch the weights in the network change. Every so often, click on the "Run" button in the test window. This will update the "sum_se" number in the Grid Log window, which is a measurement of the amount of error.

Eventually, when you get tired of clicking "Step", click the "Run" button in the Train window. The results will flicker by rather fast in the NetView, and the network will train until the stopping condition is reached. Check the points again, and observe the error numbers.

***Question 3: Draw the neural network in "standard form" as it appears after training. Does it now get all four points correct?

***Question 4: PDP++ uses the concepts "train" and "test" in a notably different way than we have in class discussion. How so?

Legalities

Much of this lab I appropriated from the instruction manual for PDP++. In order to do so, I must include the following legalese below.

Both updated through 2000 primarily by O'Reilly.

The PDP++ specific portions of the software are copyright under the following conditions:

Permission to use, copy, and modify this software and its documentation for any purpose other than distribution-for-profit is hereby granted without fee, provided that the above copyright notice and this permission
notice appear in all copies of the software and related documentation.

Permission to distribute the software or modified or extended versions thereof on a not-for-profit basis is explicitly granted, under the above conditions. HOWEVER, THE RIGHT TO DISTRIBUTE THE SOFTWARE
OR MODIFIED OR EXTENDED VERSIONS THEREOF FOR PROFIT IS *NOT* GRANTED EXCEPT BY PRIOR ARRANGEMENT AND WRITTEN CONSENT OF THE COPYRIGHT HOLDERS.

The TypeAccess/C-Super-Script (TA/CSS) portions of the software are copyright under the following conditions:

Permission to use, copy, modify, and distribute this software and its documentation for any purpose is hereby granted without fee, provided that the above copyright notice and this permission notice appear in all copies of
the software and related documentation.

Note that the PDP++ software package, which contains this package, has a more restrictive copyright, which applies only to the PDP++-specific portions of the software, which are labeled as such.

Note that the taString class, which is derived from the GNU String class, is Copyright (C) 1988 Free Software Foundation, written by Doug Lea, and is covered by the GNU General Public License, see ta_string.h. The
iv_graphic library and some iv_misc classes were derived from the InterViews morpher example and other InterViews code, which is Copyright (C) 1987, 1988, 1989, 1990, 1991 Stanford University Copyright (C) 1991
Silicon Graphics, Inc.

THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY WARRANTY OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE FOR ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES
WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT OF OR
IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.