Perceptrons

By Simon D. Levy

In the last issue of Extropy, I promised a review of Minsky and Papert’s classic work Perceptrons (1969/1987). Looking over that book, I realized that it was too mathematically oriented to be of interest to most Extropy readers (including me). Therefore, I have chosen instead to focus on a description of what a perceptron is and what it can and cannot do. With the background given in the present article, anyone interested in pursuing the mathematics of perceptrons will be in a good position to tackle Minsky and Papert’s book.

A perceptron is a computational device capable of a variety of learning tasks. Its name derives, I would guess, from the first such task for which it was designed, the task of perceiving, or recognizing, a pattern. A generic perceptron looks something like this:

Figure 1

In this diagram, the i’s are binary-valued inputs to the perceptron. (“Binary” means “having two and only two possible values” These values are typically represented as On/Off and 1/0). The w’s are weights assigning an importance to each input, the sigma is a summing operation, and the theta is a threshold value. A perceptron work as follows: (1) take each input; (2) multiply each input by its weight; (3) add all the results from (2); (4) if the results from (3) exceeds theta, answer “yes” (recognition); otherwise, answer “no” (non-recognition).

EXTROPY

#5 - Winter Issue, 1990

3 1

If all this seems a bit abstract, consider an example. Say we want to design a perceptron to recognize the letter T in a string of letters. One way to do this would be to set up a letter-sized visual grid to pass over the string (See Figure 2, below).

Figure 2

i₁	i₂	i₃
i₄	i₅	i₆
i₇	i₈	i₉

Figure 3

i₁	i₂	i₃
i₄	i₅	i₆
i₇	i₈	i₉

Each box in the grid would form an input to our perceptron. For the letter T, the inputs (boxes) i₁, i₂, i₃, i₅, and i₈ should get a heavier weighting, since it is in those boxes that most of the ink for the T is likely to be found (see Figure 3, above). (If you were building a letter-recognizing perceptron for real, you would probably want to have many more inputs — i.e., more fine-grained input — than shown here. Since the inputs are binary, the level of detail created with only nine inputs would probably be too coarse.)

So the question is, how do we set the weights (w’s) and the threshold (theta) so as to get the best recognition? Here is where the real power of the perceptron reveals itself: There is a simple algorithm (procedure) for “training” the perceptron to recognize a pattern. This algorithm is as follows (Rosenblatt 1959):

(1) Initialize the weights and the threshold theta to some arbitrary (random) values. (2) Take the sum over ( k ) of ( w_{k}i_{k} ) (ie, take each input times its weight, and add the results). (3) If the sum from (2) is greater than theta, set the output equal to 1; otherwise, set the output equal to zero.

EXTROPY

#5 - Winter Issue, 1990

3 2

(4) Compare the output from (3) with the “target” value for the current pattern. Call the difference between these two values (target minus actual output) delta. (5) Obtain a new value for the threshold theta by subtracting delta from the current theta. (6) Obtain a new value for each weight ( w_{k} ) by adding delta times ( i_{k} ) to ( w_{k} ). (7) Repeat steps (2) through (6) until delta reaches zero.

A few things are worth pointing out at this point. First, note that steps (5) and (6) form the “learning” stage of the algorithm, the stage at which the perceptron modifies itself to get closer to producing the correct response (i.e., output) for the input pattern. Step (5) adjusts the threshold based on the “wrongness” of the output, and step (6) adjusts each weight based on the “importance” of its input. That’s all there is to it.

Second, observe the generality of the algorithm: It can be trained on a pattern having many variants, such as the letter T, by changing the “token” of the pattern (e.g., T’s written by different people) on each repetition of steps (2) through (6). It can also be trained on an invariant pattern, such as the Boolean functions described below. The robustness of the perceptron, that is, its ability to deal with a varying pattern, can be attributed in part to the setup of the weights and inputs: the values of w’s will, in most cases, be the set of real numbers. Hence, the degree to which a given input unit (box) contributes to the pattern is decided by how often that unit is activated (colored-in by ink) in the tokens.

Third, and most important from a computational perspective, is the “Perceptron Convergence Theorem” proved by Minsky and Papert. This theorem says that, if a mapping (a “correct” theta and set of of w’s) exists between the input and output, the values of the w’s and of theta are guaranteed to converge (reach a stable value) in a finite number of iterations (repetitions of the algorithm). In other words, the perceptron will always learn to recognize the pattern in a finite amount of time!

Two input/output patterns solvable by a perceptron are the Boolean AND and OR functions familiar to students of computer science. In their commonest form, these and other Boolean functions take two binary inputs and yield one binary output. The truth tables (input/output relations) for these two functions are as follows:

AND:

input	output
0 0	0
0 1	0
1 0	0
1 1	1

OR:

input	output
0 0	0
0 1	1
1 0	1
1 1	1

EXTROPY

#5 - Winter Issue, 1990

3 3

The AND function corresponds to the notion that two conditions must be met for something to happen; e.g., you must have gasoline and a battery in your car to start it. In the OR function, satisfying either condition, or both, is sufficient; e.g., you need and umbrella or a raincoat to stay dry in a thunderstorm, but having both will work too.

Perceptrons for the AND and OR functions could have the following setup:

Figure 4

AND

$$(0 \times 0.5) + (0 \times 0.5) = 0.0 < 0.6 \rightarrow 0$$

$$(0 \times 0.5) + (1 \times 0.5) = 0.5 < 0.6 \rightarrow 0$$

$$(1 \times 0.5) + (0 \times 0.5) = 0.5 < 0.6 \rightarrow 0$$

$$(1 \times 0.5) + (1 \times 0.5) = 1.0 > 0.6 \rightarrow 1$$

OR

$$(0 \times 0.5) + (0 \times 0.5) = 0.0 < 0.4 \rightarrow 0$$

$$(0 \times 0.5) + (1 \times 0.5) = 0.5 > 0.4 \rightarrow 1$$

$$(1 \times 0.5) + (0 \times 0.5) = 0.5 > 0.4 \rightarrow 1$$

$$(1 \times 0.5) + (1 \times 0.5) = 1.0 > 0.4 \rightarrow 1$$

The Perceptron Convergence Theorem tells us that, by showing that a mapping exists for these to functions, we know that the perceptrons could learn the mapping. If you doubt this, try the algorithm on a piece of paper. It really works!

Unfortunately, things are not as good as they might seem. There is in fact a simple Boolean function, the XOR (eXclusive-OR) function, which no perceptron can learn. The XOR function is what is usually meant by the English word “or” — in other words, the output is true if either of its inputs, but not both, is true. (When a policeman yells “stop, or I’ll shoot,” we don’t expect him to be using the Boolean OR!) The truth table for XOR is as follows:

EXTROPY

#5 - Winter Issue, 1990

3 4

XOR:

input	output
0 0	0
0 1	1
1 0	1
1 1	0

In general, a perceptron is only capable of generating a mapping for functions that are linearly separable (Minsky and Papert, op. cit.). This means that, if you plot the inputs as (X,Y) coordinates in the Cartesian plane, it must be possible to use a straight line to separate inputs yielding an output of 1 (e.g., the pairs (0,1), (1,0), and (1,1) for the OR function) from inputs yielding a 0 output (the pair (0,0) for the OR function). This test works for AND and OR, but not for XOR. (A diagram would make this point obvious, but if I drew one, I could be risking copyright violation.)

Fortunately, there is a solution to “the XOR problem.” By adding an intermediate level to the perceptron — a so-called “hidden unit” — we can generate the desired mapping:

Figure 5

Essentially, the hidden unit represents an extra input to the network, an input whose value is the AND function of the actual two inputs (McClelland and Rumelhart 1988). The question then arises of how to train the new network to generate the XOR mapping. Since the perceptron algorithm described above doesn’t refer to a hidden unit, that algorithm will not work. In the next issue of Extropy, I will describe an algorithm that does work, the back-propagation algorithm.

EXTROPY

#5 - Winter Issue, 1990

3 5

References

McClelland, J.L and D.E. Rummelhart (1988). Explorations in Parallel Distributed Processing. Cambridge, Mass.: MIT Press.

(This is best introduction to PDP that I have seen, even though it is only supposed to be an exercise book for a larger work by the same authors. If you buy one PDP book, Explorations is the one to get. It comes with some neat software for the IBM PC, too.)

Minsky, and Papert (1969; updated 1987). Perceptrons. Cambridge, Mass.: MIT Press.

Rosenblatt, F. (1959). Two Theorems of Statistical Separability in the Perceptron. In Mechanisms of Thought Processes: Proceedings of a Symposium Held at the National Physical Laboratory, November 1958. Vol. 1 (pp. 421-456). London: HM Stationery Office.

Our Enemy, ‘The State’

KGB trainee manual: ‘You must think of humanity — past, present, and future — as one great body that requires surgery. You cannot perform surgery without severing membranes, destroying tissue, spilling blood. Similarly, in intelligence we sometimes destroy individuals who are expendable tissues in the body of humanity. Occasionally we must perform unpleasant acts, even kidnapping and liquidation. But none of this is immoral. All acts that further socialism are moral acts.’ (Reported in John Barron, KGB: The Secret Work of Soviet Agents, p. 366)

Max Stirner: ‘I am the deadly enemy of the State, which always hovers between the alternatives, it or I. Therefore it strictly insists not only on not letting me have a standing, but also on keeping down what is mine. In the State there is no property, no property of the individual, but only State property… But, in opposition to the State, I feel more and more clearly that there is still left in me a great might, the might over myself, over everything that pertains only to me and that exists only in being my own.’ (The Ego and His Own, trans. Steven T. Byington [New York: Libertarian Book Club, 1963] pp. 255-256)

Randolph Bourne: ‘War is the health of the State.’ (‘The State’ in War and the Intellectuals: Essays by Randolph S. Bourne, 1915 - 1919, ed. Carl Resek [New York: Harper & Row, 1964] p. 71)

EXTROPY

#5 - Winter Issue, 1990

3 6