STEPS TOWARD ARTIFICIAL INTELLIGENCE

Marvin Minsky

 

Dept. of Mathematics, MIT

Research Lab. of Electronics, MIT.

Member, IRE

 

Received by the IRE, October 24, 1960. The author's work summarized here—which was done at the MIT Lincoln Laboratory, a center for research operated by MIT at Lexington, Mass., with the joint Support of the U. S. Army, Navy, and Air Force under Air Force Contract AF 19(604)-5200; and at the Res. Lab. of Electronics, MIT, Cambridge, Mass., which is supported in part by the U. S. Army Signal Corps, the Air Force Office of Scientific Research, and the ONR—is based on earlier work done by the author as a Junior Fellow of the Society of Fellows, Harvard University.

 

The work toward attaining "artificial intelligence'' is the center of considerable computer research, design, and application. The field is in its starting transient, characterized by many varied and independent efforts. Marvin Minsky has been requested to draw this work together into a coherent summary, supplement it with appropriate explanatory or theoretical noncomputer information, and introduce his assessment of the state of the art. This paper emphasizes the class of activities in which a general-purpose computer, complete with a library of basic programs, is further programmed to perform operations leading to ever higher-level information processing functions such as learning and problem solving. This informative article will be of real interest to both the general Proceedings reader and the computer specialist. -- The Guest Editor.

 

Summary: The problems of heuristic programming—of making computers solve really difficult problems—are divided into five main areas: Search, Pattern-Recognition, Learning, Planning, and Induction. Wherever appropriate, the discussion is supported by extensive citation of the literature and by descriptions of a few of the most successful heuristic (problem-solving) programs constructed to date.

 

The adjective "heuristic," as used here and widely in the literature, means related to improving problem-solving performance; as a noun it is also used in regard to any method or trick used to improve the efficiency of a problem-solving system. A "heuristic program," to be considered successful, must work well on a variety of problems, and may often be excused if it fails on some. We often find it worthwhile to introduce a heuristic method, which happens to cause occasional failures, if there is an over-all improvement in performance. But imperfect methods are not necessarily heuristic, nor vice versa. Hence "heuristic" should not be regarded as opposite to "foolproof"; this has caused some confusion in the literature.

 

INTRODUCTION

 

A VISITOR to our planet might be puzzled about the role of computers in our technology. On the one hand, he would read and hear all about wonderful "mechanical brains" baffling their creators with prodigious intellectual performance. And he (or it) would be warned that these machines must be restrained, lest they overwhelm us by might, persuasion, or even by the revelation of truths too terrible to be borne. On the other hand, our visitor would find the machines being denounced on all sides for their slavish obedience, unimaginative literal interpretations, and incapacity for innovation or initiative; in short, for their inhuman dullness.

 

Our visitor might remain puzzled if he set out to find, and judge for himself, these monsters. For he would find only a few machines mostly general-purpose computers), programmed for the moment to behave according to some specification) doing things that might claim any real intellectual status. Some would be proving mathematical theorems of rather undistinguished character. A few machines might be playing certain games, occasionally defeating their designers. Some might be distinguishing between hand-printed letters. Is this enough to justify so much interest, let alone deep concern? I believe that it is; that we are on the threshold of an era that will be strongly influenced, and quite possibly dominated, by intelligent problem-solving machines. But our purpose is not to guess about what the future may bring; it is only to try to describe and explain what seem now to be our first steps toward the construction of "artificial intelligence."

 

Along with the development of general-purpose computers, the past few years have seen an increase in effort toward the discovery and mechanization of problem-solving processes. Quite a number of papers have appeared describing theories or actual computer programs concerned with game-playing, theorem-proving, pattern-recognition, and other domains which would seem to require some intelligence. The literature does not include any general discussion of the outstanding problems of this field.

 

In this article, an attempt will be made to separate out, analyze, and find the relations between some of these problems. Analysis will be supported with enough examples from the literature to serve the introductory function of a review article, but there remains much relevant work not described here. This paper is highly compressed, and therefore, cannot begin to discuss all these matters in the available space.

 

There is, of course, no generally accepted theory of "intelligence"; the analysis is our own and may be controversial. We regret that we cannot give full personal acknowledgments here—suffice it to say that we have discussed these matters with almost every one of the cited authors.

 

It is convenient to divide the problems into five main areas: Search, Pattern-Recognition Learning, Planning, and Induction these comprise the main divisions of the paper. Let us summarize the entire argument very briefly:

 

A computer can do, in a sense, only what it is told to do. But even when we do not know exactly how to solve a certain problem, we may program a machine to Search through some large space of solution attempts. Unfortunately, when we write a straightforward program for such a search, we usually find the resulting process to be enormously inefficient. With Pattern- Recognition techniques, efficiency can be greatly improved by restricting the machine to use its methods only on the kind of attempts for which they are appropriate. And with Learning, efficiency is further improved by directing Search in accord with earlier experiences. By actually analyzing the situation, using what we call Planning methods, the machine may obtain a fundamental improvement by replacing the originally given Search by a much smaller, more appropriate exploration. Finally, in the section on Induction, we consider some rather more global concepts of how one might obtain intelligent machine behavior.

I. THE PROBLEM OF SEARCH

Summary—If, for a given problem, we have a means for checking a proposed solution, then we can solve the problem by testing all possible answers. But this always takes much too long to be of practical interest. Any device that can reduce this search may be of value. If we can detect relative improvement, then “hill-climbing” (Section l-B) may be feasible, but its use requires some structural knowledge of the search space. And unless this structure meets certain conditions, hill-climbing may do more harm than good.

 

Note 1: The adjective "heuristic," as used here and widely in the literature, means related to improving problem-solving performance; as a noun it is also used in regard to any method or trick used to improve the efficiency of a problem-solving system. A "heuristic program," to be considered successful, must work well on a variety of problems, and may often be excused if it fails on some. We often find it worthwhile to introduce a heuristic method, which happens to cause occasional failures, if there is an over-all improvement in performance. But imperfect methods are not necessarily heuristic, nor vice versa. Hence "heuristic" should not be regarded as opposite to "foolproof"; this has caused some confusion in the literature.

 

When we talk of problem solving in what follows, we will usually suppose that all the problems to be solved are initially well-defined. [1] By this we mean that with each problem we are given some systematic way to decide when a proposed solution is acceptable. Most of the experimental work discussed here is concerned with such well-defined problems as are met in theorem proving or in games with precise rules for play and scoring.

 

In one sense, all such problems are trivial. For if there exists a solution to such a problem, that solution can be found eventually by any blind exhaustive process which searches through all possibilities. And it is usually not difficult to mechanize or program such a search.

 

But for any problem worthy of the name, the search through all possibilities will be too inefficient for practical use. And on the other hand, systems like chess, or nontrivial parts of mathematics, are too complicated for complete analysis. Without complete analysis, there must always remain some core of search, or “trial and error.” So we need to find techniques through which the results of incomplete analysis can be used to make the search more efficient. The necessity for this is simply overwhelming. A search of all the paths through the game of checkers involves some 10**40 move choices [2]—in chess, some 10**120 [3]. If we organized all the particles in our galaxy into some kind of parallel computer operating at the frequency of hard cosmic rays, the latter computation would still take impossibly long; we cannot expect improvements in “hardware” alone to solve all our problems. Certainly, we must use whatever we know in advance to guide the trial generator. And we must also be able to make use of results obtained along the way.

 

Notes: McCarthy [1] has discussed the enumeration problem from a recursive-function-theory point of view. This incomplete but suggestive paper proposes, among other things, that "the enumeration of partial recursive functions should give an early place to compositions of functions that have already appeared.” I regard this as an important notion, especially in the light of Shannon's results [4] on two-terminal switching circuits—that the "average" n-variable switching function requires about 2**n contacts. This disaster does not usually strike when we construct "interesting" large machines, presumably because they are based on composition of functions already found useful. In [5] and especially in [6] Ashby has an excellent discussion of the search problem. (However, I am not convinced of the usefulness of his notion of "ultrastability," which seems to be little more than the property of a machine to search until something stops it.

 

A. Relative Improvement, Hill-Climbing, and Heuristic Connections

 

A problem can hardly come to interest us if we have no background of information about it. We usually have some basis, however flimsy, for detecting improvement; some trials will be judged more successful than others. Suppose, for example, that we have a comparator which selects as the better, one from any pair of trial outcomes. Now the comparator cannot, alone, serve to make a problem well-defined. No goal is defined. But if the comparator-defined relation between trials is “transitive” (i.e., if A dominates B and B dominates C implies that A dominates C), then we can at least define “progress,” and ask our machine, given a time limit, to do the best it can.

 

But it is essential to observe that a comparator by itself, however shrewd, cannot alone give any improvement over exhaustive search. The comparator gives us information about partial success, to be sure. But we need also some way of using this information to direct the pattern of search in promising directions; to select new trial points which are in some sense “like,” or “similar to,” or “in the same direction as” those which have given the best previous results. To do this we need some additional structure on the search space. This structure need not bear much resemblance to the ordinary spatial notion of direction, or that of distance, but it must somehow tie together points which are heuristically related.

 

We will call such a structure a heuristic connection. We introduce this term for informal use only—which is why our definition is itself so informal. But we need it. Many publications have been marred by the misuse, for this purpose, of precise mathematical terms, e.g., metric and topological. The term “connection,” with its variety of dictionary meanings, seems just the word to designate a relation without commitment as to the exact nature of the relation. An important and simple kind of heuristic connection is that defined when a space has coordinates (or parameters) and there is also defined a numerical “success function” E which is a reasonably smooth function of the coordinates. Here we can use local optimization or hill-climbing methods.

 

B. Hill-Climbing

 

Suppose that we are given a black-box machine with inputs x1, . . . xn and an output E(x1, … xn). We wish to maximize E by adjusting the input values. But we are not given any mathematical description of the function E; hence, we cannot use differentiation or related methods. The obvious approach is to explore locally about a point, finding the direction of steepest ascent. One moves a certain distance in that direction and repeats the process until improvement ceases. If the hill is smooth, this may be done, approximately, by estimating the gradient component dE/dxi separately for each coordinate. There are more sophisticated approaches—one may use noise added to each variable, and correlate the output with each input (see below)—but this is the general idea. It is a fundamental technique, and we see it always in the background of far more complex systems. Heuristically, its great virtue is this: the sampling effort (for determining the direction of the gradient) grows, in a sense, only linearly with the number of parameters. So if we can solve, by such a method, a certain kind of problem involving many parameters, then the addition of more parameters of the same kind ought not to cause an inordinate increase in difficulty. We are particularly interested in problem-solving methods that can be so extended to more problems that are difficult. Alas, most interesting systems, which involve combinational operations usually, grow exponentially more difficult as we add variables.

 

 

Multiple simultaneous optimizers search for a (local) maximum value of some function E (x1, … xn) of several parameters. Each unit Ui independently "jitters" its parameter x, perhaps randomly, by adding a variation di(t) to a current mean value mi. The changes in the quantities xi and E are correlated, and the result is used to slowly change mi. The filters are to remove DC components. This technique, a form of coherent detection, usually has an advantage over methods dealing separately and sequentially with each parameter. Cf. the discussion of "informative feedback" in Wiener [11], p133ff. A great variety of hill-climbing systems have been studied under the names of “adaptive” or “self-optimizing” servomechanisms.

 

C. Troubles with Hill-Climbing

 

Obviously, the gradient-following hill-climber would be trapped if it should reach a local peak which is not a true or satisfactory optimum. It must then be forced to try larger steps or changes. It is often supposed that this false-peak problem is the chief obstacle to machine learning by this method. This certainly can be troublesome. But for really difficult problems, it seems to us that usually the more fundamental problem lies in finding any significant peak at all. Unfortunately the known E functions for difficult problems often exhibit what we have called [7] the “Mesa Phenomenon” in which a small change in a parameter usually leads to either no change in performance or to a large change in performance. The space is thus composed primarily of flat regions or “mesas.” Any tendency of the trial generator to make small steps then results in much aimless wandering without compensating information gains. A profitable search in such a space requires steps so large that hill-climbing is essentially ruled out. The problem-solver must find other methods; hill-climbing might still be feasible with a different heuristic connection.

 

Certainly, in human intellectual behavior we rarely solve a tricky problem by a steady climb toward success. I doubt that any one simple mechanism, e.g., hill-climbing, will provide the means to build an efficient and general problem-solving machine. Probably, an intelligent machine will require a variety of different mechanisms. These will be arranged in hierarchies, and in even more complex, perhaps recursive structures. And perhaps what amounts to straightforward hill-climbing on one level may sometimes appear (on a lower level) as the sudden jumps of “insight.”

 

II. THE PROBLEM OF PATTERN RECOGNITION

 

Summary—In order not to try all possibilities, a resourceful machine must classify problem situations into categories associated with the domains of effectiveness of the machine's different methods. These pattern-recognition methods must extract the heuristically significant features of the objects in question. The simplest methods simply match the objects against standards or prototypes. More powerful “property-list” methods subject each object to a sequence of tests, each detecting some property of heuristic importance. These properties have to be invariant under commonly encountered forms of distortion. Two important problems arise here—inventing new useful properties, and combining many properties to form a recognition system. For complex problems, such methods will have to be augmented by facilities for subdividing complex objects and describing the complex relations between their parts.

 

Any powerful heuristic program is bound to contain a variety of different methods and techniques. At each step of the problem-solving process, the machine will have to decide what aspect of the problem to work on, and then which method to use. A choice must be made, for we usually cannot afford to try all the possibilities.

 

In order to deal with a goal or a problem, that is, to choose an appropriate method, we have to recognize what kind of thing it is. Thus, the need to choose among actions compels us to provide the machine with classification techniques, or means of evolving them. It is of overwhelming importance for the machine to have classification techniques, which are realistic. But “realistic- can be defined only with respect to the environments to be encountered by the machine, and with respect to the methods available to it. Distinctions which cannot be exploited are not worth recognizing. And methods are usually worthless without classification schemes that can help decide when they are applicable.

 

A. Teleological Requirements of Classification

 

The useful classifications are those which match the goals and methods of the machine. The objects grouped together in the classifications should have something of heuristic value in common; they should be “similar” in a useful sense; they should depend on relevant or essential features. We should not be surprised, then, to find ourselves using inverse or teleological expressions to define the classes. We really do want to have a grip on “the class of objects which can be transformed into a result of form Y,” that is, the class of objects which will satisfy some goal. One should be wary of the familiar injunction against using teleological language in science. While it is true `that talking of goals in some contexts may dispose us towards certain kinds of animistic explanations, this need not be a bad thing in the field of problem-solving; it is hard to see how one can solve problems without thoughts of purposes. The real difficulty with teleological definitions is technical, not philosophical, and arises when they have to be used and not just mentioned. One obviously cannot afford to use for classification a method that actually requires waiting for some remote outcome, if one needs the classification precisely for deciding whether to try out that method. So, in practice, the ideal teleological definitions often have to be replaced by practical approximations, usually with some risk of error; that is, the definitions have to be made heuristically effective, or economically usable. This is of great importance. (We can think of “heuristic effectiveness” as contrasted to the ordinary mathematical notion of “effectiveness” which distinguishes those definitions which can be realized at all by machine, regardless of efficiency.)

 

B. Patterns and Descriptions

 

It is usually necessary to have ways of assigning names to symbolic expressions—to the defined classes. The structure of the names will have a crucial influence on the mental world of the machine, for it determines what kinds of things can be conveniently thought about. There are a variety of ways to assign names. The simplest schemes use what we will call conventional (or proper) names; here, arbitrary symbols are assigned to classes. But we will also want to use complex descriptions or computed names; these are constructed for classes by processes that depend on the class definitions. To be useful, these should reflect some of the structure of the things they designate, abstracted in a manner relevant to the problem area. The notion of description merges smoothly into the more complex notion of model; as we think of it, a model is a sort of active description. It is a thing whose form reflects some of the structure of the thing represented, but which also has some of the character of a working machine.

 

In Section III, we will consider “learning” systems. The behavior of those systems can be made to change in reasonable ways depending on what happened to them in the past. But by themselves, the simple learning systems are useful only in recurrent situations; they cannot cope with any significant novelty. Nontrivial performance is obtained only when learning systems are supplemented with classification or pattern-recognition methods of some inductive ability. For the variety of objects encountered in a nontrivial search is so enormous that we cannot depend on recurrence, and the mere accumulation of records of past experience can have only limited value. Pattern-Recognition, by providing a heuristic connection which links the old to the new, can make learning broadly useful.

 

What is a “pattern”? We often use this term to mean a set of objects which can in some (useful) way be treated alike. For each problem area we must ask, “What patterns would be useful for a machine working on such problems?”

 

The problems of visual pattern-recognition' have received much attention in recent years and most of our examples are from this area.

 

C. Prototype-Derived Patterns

 

The problem of reading printed characters is a clear- cut instance of a situation in which the classification is based ultimately on a fixed set of “prototypes”—e.g., the dies from which the type font was made. The individual marks on the printed page may show the results of many distortions. Some distortions are rather systematic—such as changes in size, position, and orientation. Other distortions have the nature of noise: blurring, grain, low contrast, etc.

 

If the noise is not too severe, we may be able to manage the identification by what we call a normalization and template-matching process. We first remove the differences related to size and position—that is, we normalize the input figure. One may do this, for example, by constructing a similar figure inscribed in a certain fixed triangle (see below) or one may transform the figure to obtain a certain fixed center of gravity and a unit second central moment.

A simple normalization technique. If an object is expanded uniformly, without rotation, until it touches all three sides of a triangle, the resulting figure will be unique, so that pattern recognition can proceed without concern about relative size and position.

 

There is an additional problem with rotational equivalence where it is not easy to avoid all ambiguities. One does not want to equate “6” and “9”. For that matter, one does not want to equate (0, o), or (X, x) or the 0's in xo and xo—so that there may be context-dependency involved. Once normalized, the unknown figure can be compared with templates for the prototypes and, by means of some measure of matching, choose the best fitting template. Each “matching criterion” will be sensitive to particular forms of noise and distortion, and so will each normalization procedure. The inscribing or boxing method may be sensitive to small specks, while the moment method will be especially sensitive to smearing, at least for thin-line figures, etc. The choice of a matching criterion must depend on the kinds of noise and transformations commonly encountered. Still, for many problems we may get acceptable results by using straightforward correlation methods.

 

When the class of equivalence transformations is very large, e.g., when local stretching and distortion are present, there will be difficulty in finding a uniform normalization method. Instead, one may have to consider a process of adjusting locally for best fit to the template. (While measuring the matching, one could “jitter” the figure locally; if an improvement were found the process could be repeated using a slightly different change, etc.) There is usually no practical possibility of applying to the figure all of the admissible transformations. And to recognize the topological equivalence of pairs such as those below is likely beyond any practical kind of iterative local-improvement or hill-climbing matching procedure. (Such recognitions can be mechanized, though, by methods which follow lines, detect vertices, and build up a description in the form, say, of a vertex-connection table.)

 

The figures A, A' and B, B' are topologically equivalent pairs. Lengths have been distorted in an arbitrary manner, but the connectivity relations between corresponding points have been preserved. In Sherman (8] and Haller [391 we find computer programs which can deal with such equivalences.

 

The template-matching scheme, with its normalization and direct comparison and matching criterion, is just too limited in conception to be of much use in problems that are more difficult. If the transformation set is large, normalization, or “fitting,” may be impractical, especially if there is no adequate heuristic connection on the space of transformations. Furthermore, for each defined pattern, the system has to be presented with a prototype. But if one has in mind an abstract class, one may simply be unable to represent its essential features with one or a very few concrete examples. How could one represent with a single prototype the class of figures, which have an even number of disconnected parts? Clearly, the template system has negligible descriptive power. The property-list system frees us from some of these limitations.

 

D. Property Lists and “Characters”

 

We define a property to be a two-valued function, which divides figures into two classes; a figure is said to have or not have the property according to whether the function's value is 1 or 0. Given a number N of distinction properties, we could define as many as 2**n subclasses by their set intersections and, hence, as many as 2**2**n patterns by combining the properties with ANDs and ORs. Thus, if we have three properties, rectilinear, connected, and cyclic, there are eight subclasses and 256 patterns defined by their intersections

The eight regions represent all the possible configurations of values of the three properties "rectilinear," "connected," "containing a loop." Each region contains a representative figure, and its associated binary "Character" sequence.

 

If the given properties are placed in a fixed order then we can represent any of these elementary regions by a vector, or string of digits. The vector so assigned to each figure will be called the Character of that figure (with respect to the sequence of properties in question). (In [9] we use the term characteristic for a property without restriction to 2 values.) Thus a square has the Character (1, 1, 1) and a circle the Character (0, 1, 1) for the given sequence of properties.

 

For many problems, one can use such Characters as names for categories and as primitive elements with which to define an adequate set of patterns. Characters are more than conventional names. They are instead very rudimentary forms of description (having the form of the simplest symbolic expression—the list) whose structure provides some information about the designated classes. This is a step, albeit a small one, beyond the template method; the Characters are not simple instances of the patterns, and the properties may themselves be very abstract. Finding a good set of properties is the major concern of many heuristic programs.

 

E. Invariant Properties

 

One of the prime requirements of a good property is that it be invariant under the commonly encountered equivalence transformations. Thus for visual Pattern-Recognition we would usually want the object identification to be independent of uniform changes in size and position. In their pioneering paper 1947 Pitts and McCulloch [10] describe a general technique for forming invariant properties from noninvariant ones, assuming that the transformation space has a certain (group) structure.

 

The idea behind their mathematical argument is this: suppose that we have a function P of figures, and suppose that for a given figure F we define [F] = {F1, F2 . . .} to be the set of all figures equivalent to F under the given set of transformations; further, define P [F] to be the set {P (F1), P (F2), . . .} of values of P on those figures. Finally, define P* [F] to be AVERAGE (P [F]). Then we have a new property P* whose values are independent of the selection of F from an equivalence class defined by the transformations. We have to be sure that when different representatives are chosen from a class the collection [F] will always be the same in each case. In the case of continuous transformation spaces, there will have to be a measure or the equivalent associated with the set [F] with respect to which the operation AVERAGE is defined, say, as an integration. In the case studied in [10] the transformation space is a group with a uniquely defined Haar measure: the set [F] can be computed without repetitions by scanning through the application of all the transforms T to the given figure so that the invariant property can be defined by their integration over that measure. The result is invariant of which figure is chosen because the integration is over a (compact) group.

 

This method is proposed as a neurophysiological model for pitch-invariant hearing and size-invariant visual recognition (supplemented with visual centering mechanisms). This model is discussed also on p160 of Wiener [11].) Practical application is probably limited to one-dimensional groups and analog scanning devices.

 

In most recent work, this problem is avoided by using properties already invariant under these transformations. Thus, a property might count the number of connected components in a picture—which is invariant of size and position. Or a property may count the number of vertical lines in a picture—which is invariant of size and position (but not rotation).

 

F. Generating Properties

 

The problem of generating useful properties has been discussed by Selfridge [12]; we shall summarize his approach. The machine is given, at the start, a few basic transformations A1,...An, each of which transforms, in some significant way, each figure into another figure. A1 might, for example, remove all points not on a boundary of a solid region; A2 might leave only vertex points; A3 might fill up hollow regions, etc.

 

An arbitrary sequence of picture transformations, followed by a numerical-valued function, can be used as a property function for pictures. A1 removes all points which are not at the edge of a solid region. A2 leaves only vertex points at which an arc suddenly changes direction. The function C simply counts the number of points remaining in the picture.

 

Each sequence Ai1, Ai2 , . . . of such operations forms a new transformation, so that there is available an infinite variety. We provide the machine also with one or more “terminal" operations that convert a picture into a number, so that any sequence of the elementary transformations, followed by a terminal operation, defines a property. (Dineen [13] and Kirsch [] describe how such processes were programmed in a digital computer.) We can start with a few short sequences, perhaps chosen randomly. Selfridge describes how the machine might learn new useful properties.

 

"We now feed the machine A's and 0's telling the machine each time which letter it is. Beside each sequence under the two letters, the machine builds up distribution functions from the results of applying the sequences to the image. Now, since the sequences were chosen completely randomly, it may well be that most of the sequences have very flat distribution functions; that is, they [provide] no information, and the sequences are therefore [by definition] not significant. Let it discard these and pick some others. Sooner or later, however, some sequences will prove significant; that is, their distribution functions will peak up somewhere. What the machine does now is to build up new sequences like the significant ones. This is the important point. If it merely chose sequences at random, it might take a very long while indeed to find the best sequences. But with some successful sequences, or partly successful ones, to guide it, we hope that the process will be much quicker. The crucial question remains: How do we build up sequences “like” other sequences, but not identical? As of now we think we shall merely build sequences from the transition frequencies of the significant sequences. We shall build up a matrix of transition frequencies from the significant ones, and use them as transition probabilities with which to choose new sequences.

"We do not claim that this method is necessarily a very good way of choosing sequences—only that it should do better than not using at all the knowledge of what kinds of sequences have worked. It has seemed to us that this is the crucial point of learning." See p. 93 of [12].

 

It would indeed be remarkable if this failed to yield properties more useful than would be obtained from completely random sequence selection. The generating problem is discussed further in Minsky [14]. Newell, Shaw, and Simon [15] describe more deliberate, less statistical, techniques that might be used to discover sets of properties appropriate to a given problem area. One may think of the Selfridge proposal as a system that uses a finite-state language to describe its properties. Solomonoff [18 and [55] proposes some techniques for discovering common features of a set of expressions, e.g., of the descriptions of those properties of already established utility; the methods can then be applied to generate new properties with the same common features. I consider the lines of attack in [12], [15], [18] and [55], although still incomplete, to be of the greatest importance.

 

G. Combining Properties

 

One cannot expect easily to find a small set of properties that will be just right for a problem area. It is usually much easier to find a large set of properties each of which provides a little useful information. Then one is faced with the problem of finding a way to combine them to make the desired distinctions. The simplest method is to define, for each class, a prototypical "characteristic vector" (a particular sequence of property values) and then to use some matching procedure, e.g., counting the numbers of agreements and disagreements, to compare an unknown with these chosen prototypes.

 

The linear weighting scheme described just below is a slight generalization on this. Such methods treat the properties as more or less independent evidence for and against propositions; more general procedures (about which we have yet little practical information) must account also for nonlinear relations between properties, i.e., must contain weighting terms for joint subsets of property values.

 

I. “Bayes nets” for combining independent properties:

 

We consider a single experiment in which an object is placed in front of a property-list machine. Each property E; will have a value, 0 or 1. Suppose that there has been defined some set of object classes Fj, and that we want to use the outcome of this experiment to decide in which of these classes the object belongs.

 

Assume that the situation is probabilistic, and that we know the probability pij that, if the object is in class Fj then the i-th property Ei will have value 1. Assume further that these properties are independent; that is, even given Fj, knowledge of the value of Ei tells us nothing more about the value of a different Ek in the same experiment. (This is a strong condition—see below.) Let fj be the absolute probability that an object is in class Fi. Finally, for this experiment define V to be the particular set of is for which the Ei's are 1. Then this V represents the Character of the object! From the definition of conditional probability, we have

 

Pr(Fi,V) = Pr(V)Pr (Fj|V) = Pr(Fj)Pr(V|Fj)

 

Given the Character V, we want to guess which Fj has occurred (with the least chance of being wrong—the so-called maximum likelihood estimate); that is, for which j is Pr(Fj) the largest. Since in the above Pr(V) does not depend on j, we have only to calculate for which j is Pr(V)Pr(Fj|V) = Pr(Fj)Pr(V|Fj) the largest. Hence, by our independence hypothesis, we have to maximize

fjPpijPqij = fjPpij/qijPqij,

.

where the first product is over V and the second, over its complement. These “maximum likelihood” decisions can be made (Fig. 6) by a simple network device. [7]

 

 

"Net” model for maximum-likelihood decisions based on linear weightings of property values. The input data are examined by each "property filter” Ei. Each of these has 0 and 1 output channels, one of which is excited by each input. These outputs are weighted by the corresponding pij's, as shown in the text. The resulting signals are multiplied in the Fj units, each of which collects evidence for a particular figure class. (We could have used here log(pij), and added.) The final decision is made by the topmost unit D, who merely chooses that Fj with the largest score. Note that the logarithm of the coefficient pij/qij in the second expression of (1) can be construed as the “weight of the evidence” of Ei in favor of Fj. (See also [21] and [22].)

 

Note: At the cost of an additional network layer, we may also account for the possible cost gjk that would be incurred if we were to assign to Fk a figure really in class Fj. In this case, the minimum cost decision is given by the k for which SigjkfjPpijPqij.

 

These nets resemble the general schematic diagrams proposed in the “Pandemonium” model of [Selfridge 19, Fig. 3.] It is proposed there that some intellectual processes might be carried out by a hierarchy of simultaneously functioning submachines called 'demons'. Each unit is set to detect certain patterns in the activity of others, and the output of each unit announces the degree of confidence of that unit that it sees what it is looking for. Our Ei units are Selfridge's "data demons.” Our units Fj are his “cognitive demons”; each collects, from the abstracted data, evidence for a specific proposition. The topmost “decision demon” D responds to that one in the multitude below it whose shriek is the loudest. (See also the report in [20].)

 

It is quite easy to add to this “Bayes network model” a mechanism, which will enable it to learn the optimal connection weightings. Imagine that, after each event, the machine is told which F has occurred; we could implement this by sending back a signal along the connections leading to that F unit. Suppose that the connection or for pij or qij contains a two-terminal device (or “synapse”) which stores a number wij. Whenever the joint event (Fj, Ei = 1) occurs, we modify wij by replacing it by (wij +1)q, where q is a factor slightly less than unity. And when the joint event (Fj, Ei = 0) occurs, we decrement wij by replacing it with (wij) q. It is not difficult to show that the expected values of the wij 's will become proportional to the pij 's [and, in fact, approach pij [q/(1-q]. Hence, the machine tends to learn the optimal weighting on the basis of experience. (One must put in a similar mechanism for estimating the fj 's.) The variance of the normalized weight approaches [(1-q)/(1 +q)] pijqij; Thus a small value for q means rapid learning but is associated with a large variance, hence, with low reliability. Choosing q close to unity means slow, but reliable, learning. q is really a sort of memory decay constant, and its choice must be determined by the noise and stability of the environment much noise requires long averaging times, while a changing environment requires fast adaptation. The two requirements are, of course, incompatible and the decision has to be based on an economic compromise. (See also [7] and [21])

 

G. Using random nets for Bayes decisions:

 

The nets of Fig. 6 are very orderly in structure. Is all this structure necessary? Certainly if there were a great many properties, each of which provided very little marginal information, some of them would not be missed. Then one might expect good results with a mere sampling of all the possible connection paths w~~. And one might thus, in this special situation, use a random connection net. The two-layer nets here resemble those of the “perceptron” proposal of Rosenblatt [22]. I n the latter, there is an additional level of connections coming directly from randomly selected points of a “retina.” Here the properties, the devices which abstract the visual input data, are simple functions which add some inputs, subtract others, and detect whether the result exceeds a threshold. Equation (1), we think, illustrates what is of value in this scheme. It does seem clear that such nets can handle a maximum-likelihood type of analysis of the output of the property functions. But these nets, with their simple, randomly generated, connections can probably never achieve recognition of such patterns as “the class of figures having two separated parts,” and they cannot even achieve the effect of template recognition without size and position normalization (unless sample figures have been presented previously in essentially all sizes and positions). For the chances are extremely small of finding, by random methods, enough properties usefully correlated with patterns appreciably more abstract than are those of the prototype-derived kind. And these networks can really only separate out (by weighting) information in the individual input properties; they cannot extract further information present in nonadditive form. The “perceptron” class of machines has facilities neither for obtaining better-than-chance properties nor for assembling better-than-additive combinations of those it gets from random construction.10

 

For recognizing normalized printed or hand-printed characters, single-point properties do surprisingly well [23]; this amounts to just “averaging” many samples. Bledsoe and Browning [24] claim good results with point-pair properties. Roberts [25] describes a series of experiments in this general area. Doyle [26] without normalization but with quite sophisticated properties obtains excellent results; his properties are already substantially size- and position-invariant. A general review of Doyle's work and other pattern-recognition experiments will be found in Selfridge and Neisser [20].

For the complex discrimination, e.g., between one and two connected objects, the property problem is very serious, especially for long wiggly objects such as are handled by Kirsch [27]. Here some kind of recursive processing is required and combinations of simple properties would almost certainly fail even with large nets and long training.

 

We should not leave the discussion of decision net models without noting their important limitations. The hypothesis that the pis represent independent events is a very strong condition indeed. Without this hypothesis we could still construct maximum- likelihood nets, but we would need an additional layer of cells to represent all of the joint events V; that is, we would need to know all the Pr (Fj|V). This gives a general (but trivial) solution, but requires 2**n cells for n properties, which is completely impractical for large systems. What is required is a system which computes some sampling of all the joint conditional probabilities, and uses these to estimate others when needed. The work of Uttley [28], [29], bears on this problem, but his proposed and experimental devices do not yet clearly show how to avoid exponential growth. See also Roberts [25], Papert [21], and Hawkins [22]. We can find nothing resembling this type of analysis in Rosenblatt [22].

 

H. Articulation and Attention—Limitations of the Property-List Method

 

[Note: I substantially revised this section in December 2000, to clarify and simplify the notations.] Because of its fixed size, the property-list scheme is limited in the complexities of the relations it can describe. If a machine can recognize a chair and a table, it surely should be able to tell us that "there is a chair and a table." To an extent, we can invent properties in which some such relationships are embedded, but no formula of fixed form can represent arbitrary complex relationships. Thus, we might want to describe the leftmost figure below as,

 

 

"A rectangle (1) contains two subfigures disposed horizontally. The part on the left is a rectangle (2) that contains two subfigures disposed vertically, the upper part of which is a circle (3) and the lower a triangle (4). The part on the right . . . etc."

 

Such a description entails an ability to separate or "segment" the scene into parts. (Note that in this example, the articulation is essentially recursive; the figure is first divided into two parts; then each part is described using the same machinery.) We can formalize this kind of description in an expression language whose fundamental grammatical form is a function R(L) where F names a relation and L is an ordered list of the objects or subfigures which bear that relation to one another. We obtain the required flexibility by allowing the members of the list L to contain not only the names of "elementary" figures but also "expressions that describe subfigures. Then the leftmost scene above may be described by the expression

 

IN(box(-->(IN (box (ABOVE(cir, triangle))), IN(cir(ABOVE (-->(cir, cir), cir))))))),

 

where "IN (x, y)" means 'y is inside x,'-->(x y)" means 'X is to the left of Y,' and "ABOVE (x, y)" means 'x is above y.' This description may be regarded as an expression in a simple "list-structure" language. Newell, Shaw and Simon have developed powerful computer techniques for manipulating symbolic expressions in such languages for purposes of heuristic programming. (See the remarks at the end of Section IV. If some of the members of a list are lists, they must be surrounded by exterior parentheses, and this accounts for the accumulation of parentheses.

This description language may be regarded as a simple kind of "list-structure" language. Newell, Shaw and Simon have developed powerful computer techniques for manipulating symbolic expressions in such languages for purposes of heuristic programming. See the remarks at the end of Section IV. By introducing notation for the relations 'inside of', 'to the left of', and 'above', we construct a symbolic description. Such descriptions can be formed and manipulated by machines.

 

By abstracting out the complex relation between the parts of the figure, we can re-use the same formula to describe all three of the figures above, by using the same "more abstract" expression for all of them:

F(A, B, C, D, E, F, G, H) = IN(A, (-->(IN(B, (ABOVE (C, D))), IN(E, (ABOVE (-->(F, G, H))))))),

 

in which each particular geometric figure is replaced by one of the new variables. Thus, the left-hand figure can be represented by

 

F(box, box, cir, tri, cir, cir, cir, cir),

 

and the other two scenes can be represented by the same F with different substitutions for its variables. It is up to the programmer to decide at just what level of complexity a part of a picture should be considered "primitive". This will depend on what the description is to be used for. We could further divide the drawings into vertices, lines, and arcs. Obviously, for some applications the relations would need more metrical information, e.g., specification of lengths or angles.

 

The important thing about such "articular" descriptions is that they can be obtained by repeated application of a fixed set of pattern-recognition techniques. Thus we can obtain arbitrarily complex descriptions from a fixed complexity classification-mechanism. The new element required in the mechanism (beside the capacity to manipulate the list-structures) is the ability to articulate—to "attend fully" to a selected part of the picture and bring all one's resources to bear on that part. In efficient problem-solving programs, w e will not usually complete such a description in a single operation. Instead, the depth or detail of description will be under the control of other processes. These will reach deeper, or look more carefully, only when they have to, e.g., when the presently available description is inadequate for a current goal. The author, together with L. Hodes, is working on pattern-recognition schemes using articular descriptions. By manipulating the formal descriptions, we can deal with overlapping and incomplete figures, and several other problems of the “Gestalt” type.

 

It seems likely that as machines are turned toward more difficult problem areas, passive classification systems will become less adequate, and we may have to turn toward schemes which are based more on internally-generated hypotheses, perhaps “error-controlled” along the lines proposed by MacKay [89].

 

Space requires us to terminate this discussion of pattern-recognition and description. Among the important works not reviewed here should be mentioned those of Bomba [33] and Grimsdale, et al. [34], which involve elements of description, Unger [35] and Holland [36] for parallel processing schemes, Hebb [31] who is concerned with physiological description models, and the work of the Gestalt psychologists, notably Kohler [38] who have certainly raised, if not solved, a number of important questions. Sherman [8], Haller [39] and others have completed programs using line-tracing operations for topological classification. The papers of Selfridge [12], [43], have been a major influence on work in this general area.

 

See also Kirsch, et al. [21], for discussion of a number of interesting computer image-processing techniques, and see Minot [40] and Stevens [41] for reviews of the reading machine and related problems. One should also examine some biological work, e.g., Tinbergen [42] to see instances in which some discriminations which seem, at first glance very complicated are explained on the basis of a few apparently simple properties arranged in simple decision trees.

 

III. LEARNING SYSTEMS

 

Summary—In order to solve a new problem, one should first try using methods similar to those that have worked on similar problems. To implement this “basic learning heuristic” one must generalize on past experience, and one way to do this is to use success-reinforced decision models. These learning systems are shown to be averaging devices. Using devices that also learn which events are associated with reinforcement, i.e., reward, we can build more autonomous “secondary reinforcement” systems. In applying such methods to complex problems, one encounters a serious difficulty—in distributing credit for success of a complex strategy among the many decisions that were involved. This problem can be managed by arranging for local reinforcement of partial goals within a hierarchy, and by grading the training sequence of problems to parallel a process of maturation of the machine's resources.

 

In order to solve a new problem one uses what might be called the basic learning heuristic first try using methods similar to those which have worked, in the past, on similar problems. We want our machines, too, to benefit from their past experience. Since we cannot expect new situations to be precisely the same as old ones, any useful learning will have to involve generalization techniques. There are too many notions associated 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 Section V-B.) 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 Section 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 [44]) 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 "operant reinforcement" model.

 

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, some function of the state of the environment.

 

Suppose that on each presentation of a stimulus S an animal has to make a choice, e.g., to turn left or right, and that its probability of turning right, at the n-th trial, is pn. Suppose that we want it to turn right. Whenever it does this, we might “reward” it by applying the operator Z+:

 

Pn+1 = Z+(pn) = q pn + (1-q) 0 < q < 1

 

which moves p a fraction (1-q) of the way towards unity. (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 somewhat confusing in this regard.) If we dislike what it does we apply negative reinforcement,

 

moving p the same fraction of the way toward 0. Some theory of such "linear" learning operators, generalized to several stimuli and responses, will be found in Bush and Mosteller [45]. We can show that the learning result is an average weighted by an exponentially‑decaying time factor: Let Zn be ±1 according to whether the n-th event is rewarded or extinguished and replace pn by cn-2pn-1 so that -1<cn<1, as for a correlation coefficient. Then (with c0 = 0) we obtain by induction

and since

we can write this as.

(1)

If the term Zi 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 q:

 

(2)

 

In (1) we have again the situation described in Section II-G-1; a small value of q gives fast learning, and the possibility of quick adaptation to a changing environment. A near-unity value of q gives slow learning, but also smoothes away uncertainties due to noise. As noted in Section II-G-1, 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 pij as indicated, 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. 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., [85].

 

Samuel's coefficient-optimizing program [2] [see Section III-C, 1)], uses an 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 ~n 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 that 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 011 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 [46]. This seems to be the first major work 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 Section I-C.) 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.g., upon the solution of relevant subproblems. This machine has some such ability:

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 S 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 ZU. 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.

 

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 moves and replies. We might also limit the number of conditioned stimuli.) The heuristic idea is that any signal from the environment that 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, the scheme becomes quite powerful, in principle. There are obvious pitfalls in admitting such a degree of autonomy; the values of the system may drift to a non-adaptive 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 ability to look ahead, or plan. In order to do this we need an additional device P which, given the descriptions of a situation and an action, will predict a description of the likely result. (We will discuss schemes for doing this in Section IV-C.) 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 predicted accurate 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 mechanisms for confirmed novel expectations (or new explanations), we may find the key to simulation of intellectual motivation. See the discussion of Bernstein [48] and the more extensive discussion in the very suggestive paper of Newell, Shaw, and Simon [49]; one should not overlook the pioneering paper of Newell [50] and Samuel's discussion of the minimaxing process in [2].

 

Samuel's Program for Checkers

 

In Samuel's “generalization learning” program for the game of checkers [2] 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 [3] 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." Now, if the backing-up technique is still to be used (with the incomplete move-tree) one has to substitute for the absolute “win, lose, or draw” criterion some other “static” way of evaluating nonterminal positions. [Note: In some problems the backing-up process can be handled in closed analytic form so that one may be able to use such methods as Bellman's “Dynamic Programming” [51]. Freimer [52] gives some examples for which limited “look-ahead” doesn't work.]

 

 

"Backing-up" the static evaluations of proposed moves in a game-tree. From the vertex at the left, representing the present position in a board game radiate three branches representing the player's proposed moves. Each of these might be countered by a variety of opponent moves, and so on. According to some program, a finite tree is generated. Then the worth to the player of each terminal board position is estimated. (See text) If the opponent has the same values, he will choose to minimize the score while the player will always try to maximize. The heavy lines show how this minimaxing process backs up until a choice is determined for the present position.

The full tree for chess has the order of 10120 branches—beyond the reach of any man or computer. There is a fundamental heuristic exchange) between the effectiveness of the evaluation function and the extent of the tree. A very weak evaluation (e.g. one that just compares the player's values of pieces) would yield a devastating game if the machine could explore all continuations out to, say 20 levels. But only 6 levels, roughly within range of our presently largest computers, would probably not give a brilliant game; less exhaustive strategies perhaps along the lines of [49] would be more profitable.

 

Perhaps the simplest scheme is to use a weighted sum of some selected set of “property” functions of the positions mobility, advancement, center control, and the like. This is done in Samuel's program, and in most of its predecessors. Associated with this is a multiple-simultaneous-optimizer method for discovering a good coefficient assignment (using the correlation technique noted in Section III-A). But the source of reinforcement signals in [2] is novel. One cannot afford to play out one or more entire games for each single learning step. Samuel measures instead for each move the difference between what the evaluation function yields directly of a position and what it predicts on the basis of an extensive continuation exploration, i.e., backing-up. The sign of this error, "Delta,"" is used for reinforcement; thus the system may learn something at each move.

 

Note: It should be noted that [2] describes also a rather successful checker-playing program based on recording and retrieving information about positions encountered in the past, a less abstract way of exploiting past experience. Samuel's work is notable in the variety of experiments that were performed with and without various heuristics. This gives an unusual opportunity to really find out how different heuristic methods compare. More workers should choose (other things being equal) problems for which such variations are practicable. See p. 108 of [50].

 

D. The Credit-Assignment Problem for Learning Systems

 

In playing a complex game such as chess or checkers, or in writing a computer program, one has a definite success criterion—the game is won or lost. But in the course of play, each ultimate success (or failure) is associated with a vast number of internal decisions. If the run is successful, how can we assign credit for the success among the multitude of decisions? As Newell noted,

 

"It is extremely doubtful whether there is enough information in "win, lose or draw", when referred to the whole play of the game to permit any learning at all over available time scales.... For learning to take place, each play of the game must yield much more information. This is . . . achieved by breaking the problem into components. The unit of success is the goal. If a goal is achieved its subgoals are reinforced. If not, they are inhibited. (Actually, what is reinforced is the transformation rule that provided the subgoal.) … . This also is true of the other kinds of structure: every tactic that is created provides information about the success or failure of tactic search rules; every opponent's action provides information about success or failure of likelihood inferences; and so on. The amount of information relevant to learning increases directly with the number of mechanisms in the chess-playing machine.

 

We are in complete agreement with Newell on this approach to the problem. [See also Samuel's discussion (p. 22 of [2]) on assigning credit for a change in "Delta."]

 

It is my impression that many workers in the area of "self-organizing"" systems and "random neural nets"' do not feel the urgency of this problem. Suppose that one million decisions are involved in a complex task (such as winning a chess game). Could we assign to each decision element one-millionth of the credit for the completed task? In certain special situations we can do just this—e.g., in the machines of [22], [25] and [92], etc., where the connections being reinforced are to a sufficient degree independent. But the problem-solving ability is correspondingly weak.

 

For more complex problems, with decisions in hierarchies (rather than summed on the same level) and with increments small enough to assure probable convergence, the running times would become fantastic. For complex problems, we will have to define "success'" in some rich local sense. Some of the difficulty may be evaded by using carefully graded "training sequences"" as described in the following section.

 

Friedberg's Program-Writing Program: An important example of comparative failure in this credit-assignment matter is provided by the program of Friedberg [53], [54] to solve program-writing problems. The problem here is to write programs for a (simulated) very simple digital computer. A simple problem is assigned, e.g., "compute the AND of two bits in storage and put the result in an assigned location. "" A generating device produces a random (64-instruction) program. The program is run and its success or failure is noted. The success information is used to reinforce individual instructions (in fixed locations) so that each success tends to increase the chance that the instructions of successful programs will appear in later trials. (We lack space for details of how this is done.) Thus the program tries to find "good" instructions, more or less independently, for each location in program memory. The machine did learn to solve some extremely simple problems. But it took of the order of 1000 times longer than pure chance would expect. In part I of [54], this failure is discussed and attributed in part to what we called (Section I-C) the "Mesa phenomenon." In changing just one instruction at a time, the machine had not taken large enough steps in its search through program space.

 

The second paper goes on to discuss a sequence of modifications in the program generator and its reinforcement operators. With these, and with some "priming" (starting the machine off on the right track with some useful instructions), the system came to be only a little worse than chance. The authors of [54] conclude that with these improvements "the generally superior performance of those machines with a success-number reinforcement mechanism over those without does serve to indicate that such a mechanism can provide a basis for constructing a learning machine." I disagree with this conclusion. It seems to me that each of the "improvements" can be interpreted as serving only to increase the step size of the search, that is, the randomness of the mechanism; this helps to avoid the "mesa" phenomenon and thus approach chance behavior. But it certainly does not show that the "learning mechanism" is working--one would want at least to see some better-than-chance results before arguing this point. The trouble, it seems, is with credit-assignment. The credit for a working program can only be assigned to functional groups of instructions, e.g., subroutines, and as these operate in hierarchies, we should not expect individual instruction reinforcement to work well. (See the introduction to [53] for a thoughtful discussion of the plausibility of the scheme.) It seems surprising that it was not recognized in [54] that the doubts raised earlier were probably justified. In the last section of [54], we see some real success obtained by breaking the problem into parts and solving them sequentially. This successful demonstration using division into subproblems does not use any reinforcement mechanism at all. Some experiments of similar nature are reported in [94].

 

It is my conviction that no scheme for learning, or for pattern-recognition, can have very- general utility unless there are provisions for recursive, or at least hierarchical use of previous results. We cannot expect at learning, system- to come to handle very hard problems without preparing it with a reasonably graded sequence of problems of growing difficulty. The first problem must be one that can be solved in reasonable time with the initial resources. The next must be capable of solution in reasonable time by using reasonably simple and accessible combinations of methods developed in the first, and so on. The only alternatives to this use of an adequate "training sequence" are 1) advanced resources, given initially, or 2) the fantastic exploratory processes found perhaps only in the history of organic evolution.

 

[Note: It should, however, be possible to construct learning mechanisms which can select for themselves reasonably good training sequences from an always complex environment, by pre-arranging a relatively slow development or "maturation" of tile system's facilities. 'This might be done by pre-arranging that the sequence of goals attempted by, the primary trainer match reasonably well, at each stage, the complexity of performance mechanically available to the pattern-recognition and other parts of the system. One might be able to do much of this by simply limiting the depth of hierarchical activity, perhaps only later permitting limited recursive activity.]

 

And even there, if we accept the general view of Darlington [56] who emphasizes the heuristic aspects of genetic systems, we must have developed early in, e.g., the phenomena of meiosis and crossing-over, quite highly specialized mechanisms providing for the segregation of groupings related to solutions of subproblems. Recently, much effort has been devoted to the construction of training sequences about programming "teaching machines." Naturally, the psychological literature abounds with theories of how complex behavior is built up from simpler. In our own area, perhaps the work of Solomonoff [55], while overly cryptic, shows the most thorough consideration of this dependency, on training sequences.

 

IV. PROBLEM-SOLVING AND PLANNING

 

Summary—The solution, by machine, of very complex problems will require a variety of administration facilities. During the course of solving a problem, one becomes involved with a large assembly of interrelated subproblems. From these, at each stage, a very few must be chosen for investigation. This decision must be based on 1) estimates of relative difficulties and 2) estimates of centrality of the different candidates for attention. Following subproblem selection (for which several heuristic methods are proposed), one must choose methods appropriate to the selected problems. But for very difficult problems, even these step-by-step heuristics for reducing search will fail, and the machine must have resources for analyzing the problem structure in the large-in short, for "planning." We discuss a variety of schemes for planning, including the use of models-analogous, semantic, and abstract. Certain abstract models which I call "Character Algebras" can be constructed by the machine itself, on the basis of experience or analysis. For concreteness, the discussion begins with a description of a simple but significant system (LT) which encounters some of these problems.

 

A. The "Logic Theory" Program of Newell, Shaw and Simon

 

It is not surprising that the testing grounds for early work on mechanical problem solving have usually been areas of mathematics, or games, in which the rules are learned with absolute clarity. The "Logic 'Theory," machine of [57] and [58], called "LT", was a first attempt to prove theorems in logic, by frankly heuristic methods. Although the program was not by human standards a brilliant success (and did not surpass its designers), it stands as a landmark both in heuristic programming and in the development of modern automatic programming.

 

The problem domain here is that of discovering Proofs in the Russell-Whitehead system for the Propositional Calculus. That system is given as a set of (five) axioms and (three) rules of inference; the latter specify how certain transformations can be applied to produce new theorems from old theorems and axioms.

 

The LT program is centered on the idea of "working backwards" to find am proof. Given a theorem T to be proved, LT searches among the axioms and previously established theorems for one from which T can be deduced by a single application of one of three simple "Methods" (which embody the given rules of inference). If one is found, the problem is solved. Or the search might fail completely. But finally, the search may yield one or more "problems" which are usually propositions from which T many be deduced directly. If one of these can, in turn, be proved a the