Page images

with “learning” to justify defining the term precisely. But we may be sure that any useful learning system will have to use records of the past as evidence for more general propositions; it must thus entail some commitment or other about “inductive inference.” (See Sec. VB.) Perhaps the simplest way of generalizing about a set of entities is through constructing a new one which is an “ideal,” or rather, a typical member of that set; the usual way to do this is to smooth away variation by some sort of averaging technique. And indeed we find that most of the simple learning devices do incorporate some averaging technique—often that of averaging some sort of product, thus obtaining a sort of correlation. We shall discuss this family of devices here, and some more abstract schemes in Sec. V.

A. Reinforcement A reinforcement process is one in which some aspects of the behavior of a system are caused to become more (or less) prominent in the future as a consequence of the application of a “reinforcement operator" Z. This operator is required to affect only those aspects of behavior for which instances have actually occurred recently.

The analogy is with “reward” or “extinction” (not punishment) in animal behavior. The important thing about this kind of process is that it is “operant” [a term of Skinner (1953)]; the reinforcement operator does not initiate behavior, but merely selects that which the Trainer likes from that which has occurred. Such a system must then contain a device M which generates a variety of behavior (say, in interacting with some environment) and a Trainer who makes critical judgments in applying the available reinforcement operators. (See Fig. 8.)

Let us consider a very simple reinforcement model. Suppose that on each presentation of a stimulus S an animal has to make a choice, e.g., to

[blocks in formation]

Figure 8. Parts of an "operant reinforcement" learning system. In response to a stimulus from the environment, the machine makes one of several possible responses. It remembers what decisions were made in choosing this response. Shortly thereafter, the Trainer sends to the machine positive or negative reinforcement (reward) signal; this increases or decreases the tendency to make the same decisions in the future. Note that the Trainer need not know how to solve problems, but only how to detect success or failure, or relative improvement; his function is selective. The Trainer might be connected to observe the actual stimulus-response activity, or. in a more interesting kind of system, just some function of the state of the environment.

tum left or right, and that its probability of turning right, at the nth trial, is pr. Suppose that we want it to turn right. Whenever it does this we might “reward" it by applying the operator Z+;

Pn+1 = 2+(px) Opn + (1 - 0) 0<o<1 which moves p a fraction (1 - 0) of the way toward unity.13 If we dislike what it does we apply negative reinforcement,

Pn+1 Z_(pm) moving p the same fraction of the way toward O. Some theory of such "linear” learning operators, generalized to several stimuli and responses, will be found in Bush and Mosteller (1955). We can show that the learning result is an average weighted by an exponentially-decaying time factor: Let Zy be +1 according to whether the nth event is rewarded or extinguished and replace Pn by coa = 2pn -- 1 so that – 1 < cn < 1, as for a correlation coefficient. Then (with Co = 0) we obtain by induction

[ocr errors]
[blocks in formation]

on-Zi we can write this as


(1) If the term Z; is regarded as a product of (i) how the creature responded and (ii) which kind of reinforcement was given, then cn is a kind of correlation function (with the decay weighting) of the joint behavior of these quantities. The ordinary, uniformly weighted average has the same general form but with time-dependent e:

[ocr errors][merged small][ocr errors][merged small]

In (1) we have again the situation described in Sec. IIG1; a small value of 0 gives fast learning, and the possibility of quick adaptation to a changing environment. A near-unity value of a gives slow learning, but also smooths away uncertainties due to noise. As noted in Sec. IIGI, the response distribution comes to approximate the probabilities of rewards of the alternative responses. (The importance of this phenomenon has, I think, been overrated; it is certainly not an especially rational strategy. One reasonable alternative is that of computing the numbers Di; as indi

Properly, the reinforcement functions should depend both on the p's and on the previous reaction-reward should decrease p if our animal has just turned to the left. The notation in the literature is also somewhat confusing in this regard.

cated, but actually playing at each trial the “most likely” choice. Except in the presence of a hostile opponent, there is usually no reason to play a “mixed” strategy.4)

In Samuel's coefficient-optimizing program (1959b) (see Sec. IIIC1), there is a most ingenious compromise between the exponential and the uniform averaging methods: the value of N in (2) above begins at 16 and so remains until n = 16, then N is 32 until n = 32, and so on until n = 256. Thereafter N remains fixed at 256. This nicely prevents violent fluctuations in Cn at the start, approaches the uniform weighting for a while, and finally approaches the exponentially weighted correlation, all in a manner that requires very little computation effort! Samuel's program is at present the outstanding example of a game-playing program which matches average human ability, and its success (in real time) is attributed to a wealth of such elegancies, both in heuristics and in programming.

The problem of extinction or “unlearning” is especially critical for complex, hierarchical, learning. For, once a generalization about the past has been made, one is likely to build upon it. Thus, one may come to select certain properties as important and begin to use them in the characterization of experience, perhaps storing one's memories in terms of them. If later it is discovered that some other properties would serve better, then one must face the problem of translating, or abandoning, the records based on the older system. This may be a very high price to pay. One does not easily give up an old way of looking at things, if the better one demands much effort and experience to be useful. Thus the training sequences on which our machines will spend their infancies, so to speak, must be chosen very shrewdly to insure that early abstractions will provide a good foundation for later difficult problems.

Incidentally, in spite of the space given here for their exposition, I am not convinced that such “incremental” or “statistical” learning schemes should play a central role in our models. They will certainly continue to appear as components of our programs but, I think, mainly by default. The more intelligent one is, the more often he should be able to learn from an experience something rather definite; e.g., to reject or accept a hypothesis, or to change a goal. (The obvious exception is that of a truly statistical environment in which averaging is inescapable. But the heart of problem-solving is always, we think, the combinatorial part that gives rise to searches, and we should usually be able to regard the complexities caused by "noise" as mere annoyances, however irritating they may be.) In this connection we can refer to the discussion of memory in Miller, Galanter and Pribram (1960).15 This seems to be the first major work

1 The question of just how often one should play a strategy different from the estimated optimum, in order to gain information, is an underlying problem in many fields. See, e.g., Shubik (1960).

" See especially chap. 10.

in psychology to show the influence of work in the artificial intelligence area, and its programme is generally quite sophisticated.

B. Secondary Reinforcement and Expectation Models The simple reinforcement system is limited by its dependence on the Trainer. If the Trainer can detect only the solution of a problem, then we may encounter “mesa” phenomena which will limit performance on difficult problems. (See Sec. IC.) One way to escape this is to have the machine learn to generalize on what the Trainer does. Then, in difficult problems, it may be able to give itself partial reinforcements along the way, e.8., upon the solution of relevant subproblems. The machine in Fig. 9 has some such ability. The new unit U is a device that learns which external stimuli are strongly correlated with the various reinforcement signals, and responds to such stimuli by reproducing the corresponding reinforcement signals. (The device U is not itself a reinforcement learning device; it is more like a “Pavlovian” conditioning device, treating the Z signals as "unconditioned” stimuli and the S signals as conditioned stimuli.) The heuristic idea is that any signal from the environment which in the past has been well correlated with (say) positive reinforcement is likely to be an indication that something good has just happened. If the training on early problems was such that this is realistic, then the system eventually should be able to detach itself from the Trainer, and become autonomous. If we further permit “chaining” of the “secondary reinforcers,” e.g., by admitting the connection shown as a dotted line in Fig. 9, the scheme becomes quite powerful, in principle. There are obvious pitfalls in admitting

[merged small][merged small][merged small][merged small][merged small][ocr errors][merged small][merged small]

Figure 9. An additional device U gives the machine of Fig. 8 the ability to learn which signals from the environment have been associated with reinforcement. The primary reinforcement signals Z are routed through U. By a Pavlovian conditioning process (not described here), external signals come to produce reinforcement signals like those that have frequently succeeded them in the past. Such signals might be abstract, e.g., verbal encouragement. If the "secondary reinforcement” signals are allowed, in turn, to acquire further external associations (through, e.g., a channel Zu as shown) the machine might come to be able to handle chains of subproblems. But something must be done to stabilize the system against the positive symbolic feedback loop formed by the path Zy. The profound difficulty presented by this stabilization problem may be reflected in the fact that, in lower animals, it is very difficult to demonstrate such chaining effects.

such a degree of autonomy; the values of the system may drift to a “nonadaptive” condition. C. Prediction and Expectation The evaluation unit U is supposed to acquire an ability to tell whether a situation is good or bad. This evaluation could be applied to imaginary situations as well as to real ones. If we could estimate the consequences of a proposed action (without its actual execution), we could use U to evaluate the (estimated) resulting situation. This could help in reducing the effort in search, and we would have in effect a machine with some abivity to look ahead, or plan. In order to do this we need an additional device P which, given the description of a situation and an action, will predict a description of the likely result. (We will discuss schemes for doing this in Sec. IVC.) The device P might be constructed along the lines of a reinforcement learning device. In such a system the required reinforcement signals would have a very attractive character. For the machine must reinforce P positively when the actual outcome resembles that which was predictedaccurate expectations are rewarded. If we could further add a premium to reinforcement of those predictions which have a novel aspect, we might expect to discern behavior motivated by a sort of curiosity. In the reinforcement of mechanisias for confirmed novel expectations (or new explanations) we may find the key to simulation of intellectual motivation.16

SAMUEL'S PROGRAM FOR CHECKERS In Samuel's “generalization learning" program for the game of checkers (1959a) we find a novel heuristic technique which could be regarded as a simple example of the “expectation reinforcement” notion. Let us review very briefly the situation in playing two-person board games of this kind. As noted by Shannon (1956) such games are in principle finite, and a best strategy can be found by following out all possible continuations—if he goes there I can go there, or there, etc.—and then "backing up” or “minimaxing” from the terminal positions, won, lost, or drawn. But in practice the full exploration of the resulting colossal “move tree" is out of the question. No doubt, some exploration will always be necessary for such games. But the tree must be pruned. We might simply put a limit on depth of exploration—the number of moves and replies. We might also limit the number of alternatives explored from each position—this requires some heuristics for selection of “plausible moves."17 Now, if the backing-up technique is still to be used (with the incomplete move tree) one has to

" See also chap. 6 of Minsky (1954).

" See the discussion of Bernstein (1958) and the more extensive review and discussion in the very suggestive paper of Newell, Shaw and Simon (1958b).

« PreviousContinue »