Neurocomputing Part 3

by Simon! D. Levy

In the last issue of EXTROPY, I described the computational device known as a perceptron, and described what it could and couldn’t do. The class of problems which a perceptron cannot solve, called linearly inseparable problems, includes the XOR problem. As you may recall from the previous article, this problem requires a function that generates the following mapping from inputs to outputs:

In other words, the output is true (1) when either input, but not both, is true; otherwise, the output is false (0).

This sort of problem can be solved by adding a hidden unit to the perceptron. As illustrated below, a hidden unit is a unit that is placed between the input and the output of a neural network in order to generate the current mapping.

known as gradient descent. Gradient descent is a method of minimizing the error produced by the network, where the error is defined as the difference between what the network’s output should be and what it actually is.

To understand how gradient descent works, imagine that we have a very simple network, with only one input and one output, and hence only one weight (multiplication) between the input and its threshold. Assuming that we know what the output should be, we can plot the error as a function of this weight:

FIGURE 1

If you remember that a sigma stands for summation, that the numbers on the lines stand for multiplication, and that the bullet-shaped symbols are thresholds, you can see how this network produces the mapping for the XOR function. Essentially the purpose of the hidden unit for this particular network is to generate a value of -1 when both inputs are 1; this -1 value “cancels out” the two positive 0.5s that result in that situation. The problem is how to train the hidden unit, since the perceptron algorithm described in the last article does not refer to this unit.

A number of methods have been devised for training networks containing hidden units. One of the most common methods relies on the mathematical technique

Figure 2

The best value for the weight corresponds to a point where the error is at a minimum, in this case, a weight of 0.6.

Gradient descent is a technique for finding the quickest path to a minimum point in the error function. The idea is to find a path for which the derivative (slope) of this function is the largest (steepest), where the derivative is defined as the difference between the current value of the function and the next value we look at. By changing the weights in a direction along the steepest path, we will find the fastest route to some minimum value of the error function

EXTROPY #6

24

Summer 1990

(but not necessarily the smallest value - more on that problem later).

So, for the first error function, let’s say we start out with the weight at 0.4. Which direction should we go in? Well, the slope is steeper to the right of 0.4, so rightward is the correct direction. Once we reach the minimum error at the weight 0.6, the derivative becomes negative, because the next value is larger than the current value. Therefore, we stop moving when the weight is 0.6.

Of course, a real network will have more than one weight (the simple XOR network shown in Figure 1 has five), and the error function we plot will therefore have more than the two dimensions shown in Figure 2. Gradient descent does what it’s supposed to regardless of the number of weights. (I find the idea of “skiing toward the minimum in a multi-dimensional space kind of neat, even if it is impossible for my mind to visualize a space of more than three dimensions!)

The question is how to find the steepest slope in our multi-dimensional space. Looking everywhere in the space would take an impossibly long time. Fortunately, it has been mathematically proven that a more general version of the perceptron-learning rule (which is also known as the delta rule) corresponds to gradient descent. (For a formal proof, see Chapter 8 of Rumelhart and McClelland’s Parallel Distributed Processing, MIT Press, 1988). As described in my last article, the delta rule says the following: See what the output is for the network with a particular set of inputs and weights. Take the difference (“delta”) between this output and the desired output, and multiply each weight by that difference.

The generalized delta rule says the same thing, with a couple of differences: First, the delta of a hidden unit is computed in terms of the deltas of the next units in the network (the next “layer”), and the weights connecting the hidden unit to those units. Specifically, we take each weight between the current unit and each of the next units to which it connects, and multiply this weight by the delta for that next unit. Then we add the results of all these multiplications together to get the delta for the hidden unit. For the XOR network above, the “next layer” would be the output layer. At the output layer, delta is simply the difference between the desired output and the actual output, as it was in the perceptron. In this manner, the generalized delta rule gives us a recursive procedure for computing the deltas at each layer, in terms of the deltas at the next layer, and the buck stops at the output. That’s why the technique is referred to as back propagation, because we start at the output units and work our way back through the hidden units, calculating the deltas.

The second difference between the generalized delta rule and the simple delta rule comes from the fact that the gradient descent technique looks at the slope of the error function, as illustrated in Figure 2. For a threshold, such as the thresholds shown in Figure 1, this slope is infinite, since the output of the threshold function goes from zero to a positive integer in no time at all. (See Figure 3.)

In mathematical terms, an infinite slope is undefined, so we need some other function to calculate the output of a unit. One such function is shown in Figure 4.

This function, called a logistic activation function, looks a lot like the threshold activation function in Figure 3,

Figure B here

Figure 3

Figure C here

Figure 4

EXTROPY #6

25

Summer 1990