Adaptive computing system capable of learning and discovery

• US 4,697,242 A
• Filed: 06/11/1984
• Issued: 09/29/1987
• Est. Priority Date: 06/11/1984
• Status: Expired due to Term

• Current Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Original Assignee: Board of Regents of the University of Michigan (University of Michigan)
• Inventors: Holland, John H., Burks, Arthur W.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Lastova, John R.
• Application Number:
  US06/619,349
• Time in Patent Office: 1,205 Days
• Field of Search: 364/513, 364/900, 382/34, 382/27, 382/42, 382/68
• US Class Current: 706/13
• CPC Class Codes: G06F 18/2111 by using evolutionary computational techniques, e.g. genetic algorithms
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries

Abstract

An electronic computing system capable of learning and discovery employing a language composed of conditional statements called "classifiers" which respond to and operate fixed-length binary words called "messages". Each classifier comprises a condition part which identifies the message(s) to which the classfier responds, and an action part which specifies the content of the generated message which may, in part, be a function of one or more of the input messages. An adaptive algorithm, called the "bucket brigade algorithm", tracks the history of each classifier'"'"'s performance and develops a strength value which serves as a measure of the past usefulness of that classifier in reaching a defined objective. A genetic algorithm generates new classifiers which are based on the strongest of the existing classifiers and which replace the weakest of the existing classifiers.

Claims

1. A computing system comprising, in combination,

a source of input data comprising k-bit binary message words,

a message memory for storing said input data and additional k-bit binary message words,

a classifier memory for storing a plurality of classifiers, each of said classifiers being composed of a condition part, an action part, and a strength value,

said condition part comprising one or more k-position ternary words each of which specifies a subset of the possible k-bit binary message words, and

said action part comprising at least one k-position ternary word which at least partially specifies the content of a new message word,

matching means for comparing each message word in said message memory with the condition part of each classifier in said classifier memory,

means responsive to said matching means for generating new message word whenever each of the ternary words in the condition part of a classifier is satisfied by at least one message in said message memory, and

means for increasing the strength value associated with a particular classifier whenever said particular classifier generates a new message word to which a further classifier responds by generating a message word.

2. A computing system as set forth in claim 1 further comprising, in combination,

means for decreasing the strength value associated with a given classifier whenever the given classifier responds to existing messages by generating a new message word.

3. A computing machine as set forth in claim 1 wherein the amount by which the strength value associated with said particular classifier is increased is directly related to the strength value associated with said further classifier.

4. A computing machine as set forth in claim 2 wherein the amount by which a strength value is decreased is directly related to the current magnitude of said strength value.

5. A computing machine as set forth in claim 1, 2, 3 or 4 comprising, in combination,

means for selecting a pair of said classifiers in said classifier memory having high relative strength values,

means for forming a new pair of classifiers, each of said new pair comprising portions copied from each of said selected pair, and

means for replacing two classifiers in said classifier memory having low relative strength values with said new pair of classifiers.

6. A computing machine as set forth in claims 1, 2 or 3 wherein said matching means comprises an associative memory for at least partially comparing said messages and said classifiers simultaneously and in parallel.

7. A computing system comprising, in combination,

a message store for storing a plurality of k-position binary message words,

a classifier store for storing a plurality of classifiers, each of said classifiers comprising a condition part composed of at least one k-position ternary condition word which specifies a subset of possible message words and an action part which at least partially specifies the content of an output message,

means for comparing said condition words with said message words,

means for assigning an initial strength value to each of said classifiers,

means responsive to said comparing means for forming a bid value whenever the specifications contained in the condition part of a given classifier is satisfied by one or more messages in said message store, said bid value being directly related to the current strength value of said given classifier and inversely related to the size of the subset of possible messages specified by the condition part of said classifier,

means for producing new set of message words as specified by the action part of those particular classifiers which generated high relative bid values,

means for reducing the current strength value assigned to each of said particular classifiers, and

means for increasing the current strength value of those classifiers which produced a message word which satisfied the specifications of the condition part of one of said particular classifiers.

8. A computing system as set forth in claim 7 wherein the amount by which the current strength value of each of said particular classifiers is increased is directly related to the magnitude of the bid value formed by that classifier.

9. An adaptive method for processing input data from an external source into output data having desired characteristics comprising, in combination, the steps of

(a) storing in a message memory of plurality of messages each comprising a sequence of binary digits, at least some of said messages containing information derived from said input data,

(b) storing in a classifier memory a plurality of classifier each constituting an instruction governing the performance of a predetermined message translation step and each comprising, in combination,

a condition part for identifying a class of said messages in said message memory which are to be translated by said translation step to form result messages,

an action part specifying the functional relationship between messages in said class and said result messages, and

a strength value;

(c) performing the message translation steps defined by said classifiers to produce a group of said result messages;

(d) replacing the messages stored in said message memory with messages from said group produced by classifiers having higher relative strength values; and

(e) increasing the strength value of each classifier which produces a result message which is placed in said message memory and which in turn satisfies the condition part of a classifier to produce a further result message which is placed in said message memory.

10. An adaptive method as set forth in claim 9 wherein said step of replacing the messages stored in said message memory comprises the steps of

forming a bid value associated with each of said result messages which is directly related to the magnitude of strength value and the specificity of the condition part of the classifier which produced said associated message, and

replacing the messages stored in said message memory with those result messages having higher associated bid values.

11. An adaptive method as set forth in claims 9 or 10 further including means for periodically replacing classifiers in said classifier memory having relatively low strength values with modified versions of classifiers having relatively high strength values.

12. An adaptive method as set forth in claim 11 wherein each of said modified versions is formed by combining portions of two or more classifiers having relatively high strength values.

13. An adaptive computing method as set forth in claim 9 or 10, wherein said messages comprise a sequence of k-position binary words using the symbols "1" and "0" and said condition part of each of said classifiers comprises one or more k-position ternary words using the symbols "1", "0" and "#" and wherein said condition part specifies those messages having a "1" symbol at the digit positions where "1" symbols exist in said condition part, having "0" symbols at digit positions where "0" symbols exist in said condition part, and having either "1" or "0" symbols at digit positions where "#" symbols exist in said condition part.

14. An adaptive computing method as set forth in claim 13 wherein the number of "#" symbols in said condition part provides a specificity value for said condition part and wherein said step of replacing the messages includes means for replacing the messages stored in said message memory with messages from said group produced by classifiers having higher combined relative strength values and specificity values.

15. An adaptive computer system for processing input data from an external source to yield output data having predetermined characteristics, said system comprising, in combination:

a message memory for storing messages, each of said messages comprising a unit of information represented as a sequence of binary digits;

a classifier memory for storing a plurality of classifiers each consisting of

a condition part for specifying the attributes of one or more selected classes of messages stored in said message memory,

an action part for specifying the manner in which the messages in said selected classes are to be translated into output messages, and

a strength value indicative of the past utility of said classifier;

input means for converting said input data from said external source into one or more messages and for storing said messages in said message memory;

processing means for performing a plurality of independent procedures each in accordance with a respective one of said plurality of classifiers to generate a collection of result messages, and

reward means responsive to selected result messages for increasing the strength value associated with those classifiers which produced said selected result messages.

16. An adaptive computer system as set forth in claim 15 wherein said selected result messages are messages which are specified by the condition parts of other classifiers.

17. An adaptive computer system as set forth in claim 15 or 16 further inluding means connected to said classifier memory for replacing classifiers having low strength values with modified versions of classifiers having high relative strength values.

18. An adaptive computer system as set forth in claim 17 wherein each of said modified versions contains information derived from one or more existing classifiers having high relative strength values.

22. An adaptive computing system as set forth in claims 19 or 18 further including means for decreasing the strength value of each classifier which produces a result message which is made available for further processing by said processing means.

37. An adaptive computing system as set forth in claims 9, 15, 19 or 26 wherein said condition part defines at least first and second classes of messages and wherein said classifier translates each message in said first class into an output message provided at least one message exists in said second class.

38. An adaptive computing system as set forth in claims 9, 15, 19 or 26 wherein said condition part of at least some of said classifiers defines at least first and second classes of messages and further including a negation indicia associated with said second class and wherein said classifier translates each message in said first class into an output message provided no messages exist in said second class.

39. An adaptive computing system as set forth in claims 9, 15, 19 or 26 wherein said action part of at least some of said classifiers includes an operation identifier for specifying a functional relationship between information contained in one or more messages satisfying the condition part of said classifier and information contained in the output message generated by said classifier.

40. An adaptive computing system as set forth in claims 9, 15, 19 or 26 wherein each given one of said messages has associated therewith an index value which identifies the classifer which produced said given message.

19. An adaptive computing system comprising, in combination,

a message memory for storing a plurality of messages, each message being represented by a sequence of binary digits;

a classifier memory for storing a plurality of classifiers, each such classifier consisting of;

a condition part identifying selected messages which are to be read from the message memory and processed into result messages,

an action part which specifies the functional relationship between said selected messages and said result messages, and

a strength value; and

processing means for translating messages in said message store in accordance with each of said classifiers, said processing means including means for increasing the strength value of any classifier which creates a result message which is itself specified by the condition part of a second classifier and translated into a further result message which is placed in said message store.

20. An adaptive computing system as set forth in claim 19 wherein said processing means further includes

means for forming a bid value associated with every result message based at least in part on the strength value of the classifier which created said result message, and

means included in said processing means for translating only those result messages having high associated bid values relative to the bid values of other result messages.

21. An adaptive computing system as set forth in claims 19 or 20 wherein said processing means further includes means for replacing classifiers having low strength values with modified versions of classifiers having higher strength values.

23. An adaptive computing system as set forth in claim 19 wherein said processing means further includes, in combination,

means for forming a bid value associated with each message generated by a given classifier, said bid value being related to the strength of said given classifier, and

means for translating only those messages which:

(a) are identified by the condition part of one or more classifiers, and

(b) having bid value greater than a threshold value.

24. An adaptive computing system as set forth in claim 23 wherein said means for increasing the strength value increases said strength value by an amount related to said bid value.

25. An adaptive computing system as set forth in claim 23 or 24 including means for decreasing the strength value of each of said given classifiers by the amount of said bid value whenever said given classifier generates an output message having an associated bid value greater than said threshold value.

26. An adaptive computing system for processing input information from an external source into output information delivered to external utilization means comprising, in combination,

a message memory for storing a plurality of messages, each of said messages comprising a binary sequence of digits,

a classifier memory for storing a plurality of classifiers each having a condition part, an action part and a strength value, said condition part specifying the attributes of a class of messages in said message memory which are to be translated into output messages in accordance with information contained in said action part,

means establishing a sequence of major machine cycles,

processing means operative during each of said major cycles for generating an output message whenever the condition part of any of said classifiers is satisfied by one or more messages in said message memory,

means for replacing the messages present in said message memory at the start of a given major cycle with the output messages generated during said given major cycle,

input message handling means connected to said external source for placing input messages into said message memory prior to at least one of said major cycles,

output message handling means for selecting output messages having predetermined desired characteristics from said message memory and delivering said output messages to said external utilization means, and

means for increasing the strength value of each classifier which generates a message which, during the next major cycle, is delivered to said external utilization means or causes the generation of a further output message by satisfying the condition part of a classifier.

27. An adaptive computing system as set forth in claim 26 wherein said processing means comprises a plurality of concurrently operating parallel processors.

28. An adaptive computing system as set forth in claim 26 wherein said processing means includes means for generating output messages only in response to those messages which were generated by classifiers having higher relative strength values.

29. An adaptive computing system as set forth in claim 26 or 28 wherein said means for replacing the messages present in said message memory further includes means for decreasing the strength value of each classifier which supplied a replacement message to said message memory.

30. An adaptive computing system as set forth in claims 26 or 28, wherein said means for replacing messages in said message memory further includes

means for forming a bid value associated with each given one of said output messages having a magnitude related to the strength of the classifier which produced said given message, and

means for replacing messages in said message memory with those messages having higher associated bid values.

31. An adaptive computing system as set forth in claim 30 wherein said means for forming said bid value includes means for forming a bid value having a magnitude directly related to both the strength value of the classifier which produced said given message and inversely related to the size of the class of messages to be translated as specified by the action part of the classifier which produced said given message.

32. An adaptive computing system as set forth in claim 26 wherein said processing means further includes means for generating output messages only in response to those messages which were generated by classifiers having higher relative strength values and having condition parts satisfied by a relatively restricted class of messages.

33. An adaptive computing system as set forth in claim 26 including means for replacing classifiers having lower relative strength values with substitute classifiers.

34. An adaptive computing system as set forth in claim 33 wherein said substitute classifiers are formed by combinations of portions of classifiers having high relative strength values.

35. An adaptive computing system as set forth in claim 33 wherein said substitute classifiers are formed by modifying existing classifiers having high relative strength values.

36. An adaptive computing system as set forth in claim 26 wherein said message memory takes the form of an associative memory and wherein said processing means during each of said major cycles presents the condition part of each of said classifiers in succession for comparison against the messages stored in said associative memory.