Associative memory search system4366551Abstract A knowledge storage and retrieval method is performed to result in a single address number of a storage region which represents a large quantity of information. A first character of a data sequence and a starting number are directed into a two-position buffer to form an input matrix. The storage locations of the storage region are addressed to see if the matrix is found in the storage region. If the matrix is found, the address number of the storage location of the storage region at which it is found is then stored in the second position of the buffer region. Then the next data character is directed into the first position of the buffer region and the searching step is repeated. If the matrix in the buffer region is not found in the storage region, the matrix is stored in a free storage location of the storage region and the address number of the free storage location is directed into the second position of the buffer. The next data character is moved into the first position and the searching step is repeated. Eventually, all of the data characters of a data sequence will be stored and the address number representing a storage location of the last-to-be stored data character will represent all of the data characters of the data sequence that were stored. Claims I claim: Description BACKGROUND OF THE INVENTION
______________________________________
Label Operation
______________________________________
START The electronic control circuit will initialize its internal
15 MATRIX REGISTER by setting its POINTER value
to the starting node of the network. In
most cases this will be ADDRESS 0 but it may be
any ADDRESS because several networks may be
interleaved in the same memory device.
A special STOP code must be stored in the memory
device at the location specified by the starting
ADDRESS. The code is arbitrary but must be
recognizable by the controlling circuit.
LOOP The controlling circuit (micro-processor) will
16 wait for the arrival of data values from the
outside world.
The data value must be a digital number which may
be of any format such as written (ASCII) characters.
17 The arriving character is first examined to
determine if it represents an END code which
indicates the end of the input sequence.
For example, in written text it would be
characters like space, comma, full stop,
question mark, etc.
If it is one of these END codes the current
POINTER value in the MATRIX REGISTER is the
ADDRESS (18) number which is the final product
of this procedure. The program would return
to label START 19.
If it is not an END code the input character
is loaded into the GATE portion of the MATRIX
REGISTER 20.
21 The controlling circuit will search the network
memory device to determine if any memory
ADDRESS location contains a pattern which is
identical to the current content of the MATRIX
REGISTER.
The memory search may be performed by sequen-
tially scanning the memory locations or by direct
access to a content addressable memory device.
The scanning sequence is in forward direction
only and one complete scan of the entire
memory device is always sufficient to recognize
or learn the entire input sequence.
If a memory location is found which content
matches the current content of the MATRIX
REGISTER 22 the ADDRESS of that memory
location is loaded into the POINTER portion
of the MATRIX REGISTER 23. The operation
sequence would branch back to Label LOOP 24.
If a matching pattern is not found in the
memory device 25 a new network node must
be created. This is accomplished by storing
the present content of the MATRIX REGISTER
in the next free memory location. This may
be the next memory location on the end of
the presently used portion of the memory
field. The ADDRESS 26 of that memory location
is then loaded into the POINTER portion of
the MATRIX REGISTER 23 and the operation
sequence will branch back to label LOOP 24.
______________________________________
As an example, the following text together with FIG. 7
will show how the network is generated from the steps in the
preceding process. It will be assumed here that the word ROSE
was previously learned and the word ROBOT is not yet learned.
The example shows how the second word ROBOT is learned.
______________________________________
25 The matrix register originally contains the POINTER "0"
since the network extrance is in the case ADDRESS 0.
26 The first input character R is loaded into the GATE
portion of the MATRIX register.
27 A scan of the memory device determines that a pattern
of GATE R and POINTER 0 is stored in ADDRESS 1.
ADDRESS 1 is loaded into the POINTER portion of the
MATRIX register and the circuits await the arrival
of the next character.
28 The next character GATE 0 and POINTER 1 are located
in the memory device ADDRESS 2.
29 ADDRESS 2 is loaded into the POINTER portion of the
MATRIX register.
30 The next character GATE B and POINTER 2 cannot be found
in the memory device. The content of the MATRIX
register containing GATE B and POINTER 2 is stored in
the next free available ADDRESS location in the memory
device.
31 In this example it is ADDRESS 5. A new node is therewith
created and the POINTER value in the MATRIX register is
loaded with ADDRESS 5.
32 The next two characters O and T are similarly used to
create new nodes at the end of the currently used
memory field. It is not really requrired to search
the memory field since once storage is initiated no
matching matrix patterns in the memory will be found.
33 The END code input indicates that the present POINTER
value is the ADDRESS output number which is the final
result of this procedure.
34 Address number 7 is the output for the entire word
ROBOT. This ADDRESS 7 totally identified the word
ROBOT and any future input of that word will always
lead to ADDRESS 7. Any unique input word will generate
a unique ADDRESS number. A word once learned will be
recognized but never learned again.
The network will expand indefinitely to absorb new
words but since more and more patterns are already
stored the memory requirements for subsequent words
will decrease until memory requirement will almost
saturate.
______________________________________
The previous description should explain the steps to assemble a learning network and the automatic process to expand the network to absorb new input patterns. The resulting stored infinite dimensional network is also shown. (35). GATE and POINTER numbers consist of digital (binary) numbers which are stored in a common memory device. WORD RETRIEVAL FROM A LEARNING NETWORK A learning network converts any data input sequence of any arbitrary length into a single ADDRESS number. The ADDRESS number totally identifies each input sequence and may be used to retrieve it at a later time. Turning now to FIG. 8 which shows a flow chart of this process which will now be explained in detail.
______________________________________
Label Operation
______________________________________
START The control circuit waits for the input of the
36 ADDRESS number which is supplied either direct
or is received from previous network. In
the example it was ADDRESS number 4 for ROSE
and 7 for ROBOT.
37 This ADDRESS number is used for the first
operation
LOOP The control circuit will fetch the content of
38 the memory location specified by the ADDRESS
number. The memory word is fetched
or read from memory device and
loaded into the MATRIX register
39 The MATRIX register is examined to determine
if it contains the STOP code which
denotes the network entrance. The control
circuit may alternately hold the ADDRESS of the
network entrance and terminate the
sequence when this ADDRESS is detected.
40 If either of these conditions is true, the
sequence is terminated because the whole output
pattern is retrieved at this time. The program
would branch back to Label START. (41)
The MATRIX register now contains the GATE and
POINTER values which were previously fetched
from the memory device.
The GATE portion of the MATRIX register contains
the output data which is sent out to some
external output device such as a typewriter. (42)
The POINTER portion of the MATRIX register 43
contains the ADDRESS of the next word in the
memory device which contains the next output
characater and another POINTER. The ADDRESS
number is noted and the program branches back
to Label LOOP. (44)
______________________________________
The above procedure will retrieve the entire data sequence from the ADDRESS number but in reverse order. In the example ADDRESS number 4 would result in ESOR and ADDRESS number 7 in TOBOR. This may easily be remedied by adding a first-in-last-out buffer in the control circuit. The following text and FIG. 9 will describe as an example of how the word ROBOT is retrieved from the network in FIG. 7 (35) by its ADDRESS number 7.
______________________________________
(45) The input ADDRESS number 7 is used to
address the memory device and to read or
fetch the memory content of ADDRESS 7. The
content of this memory location is loaded
into the MATRIX register.
The MATRIX register now contains a GATE
value T (46) and a POINTER value 6. The
GATE character T is the last letter of the
word ROBOT. It is sent to the output
device.
The POINTER portion of the MATRIX register
contains the ADDRESS of the next location in
the memory device. In the example the next
memory device ADDRESS location 6 is fetched
and loaded into the MATRIX register. (47)
The MATRIX register now contains the next
(GATE) character 0 and the next POINTER 5.
This process is repeated until ADDRESS 0
is reached (48). The sequence is then
complete and the entire word ROBOT should
be retrieved in reverse order.
______________________________________
The above description should explain how a data pattern sequence once stored in a learning network can be retrieved from its unique ADDRESS number. BI-POLAR NETWORKS These networks perform the associative function by connecting nodes in separate networks. In most practical systems an input pattern must be connected to some output pattern such as Question to Answer, Input to Output, command to execution, etc. This connection function is implemented by the multi-polar networks which connect certain nodes in other networks. FIG. 10 shows a standard BI-POLAR network node. The input POINTER PI represents a node (ADDRESS) in some input network. As such it represents an input such as a question encoded into a single ADDRESS number. The INPUT GATE GI represents some system condition which is connected with the selection of the output response. It is a complex pattern which is converted into a single ADDRESS number by a separate status network. In very simple systems the INPUT GATE may not be required. As an example of the functioning of the INPUT GATE consider how the answer to a question given to a human is dependent on such emotional states as hurry, rage, emergency, talking to a child, a friend or stranger. A computer must similarly select its response according to its system conditions. The OUTPUT GATE GO represents a factor in selecting an output sequence depending on the condition of the output device. It is a complex pattern encoded into a single address number by a separate output status network. The OUTPUT GATE may not be required in very simple systems. As an example, consider how a normal output sequence may be modified if the output device is not available or defective. Another alternate output sequence may then be selected. The Output POINTER PO is a node (ADDRESS) in the output network which represents the desired output response. It is a single address number which was derived by encoding the complex output pattern as described in "A Learning Network". This number is subsequently used to retrieve the output pattern sequence as described in "Word Retrieval from a Learning Network". The Bi-Polar Networks are distinct in that the node ADDRESS number is not directly used but serves only to guide the search and store operations of the memory device. As specified earlier, the relationships of concepts also constitute knowledge but no new concept is created in the process. The terms INPUT POINTER and OUTPUT POINTER are used only for convenience. Their function may be reversed. For example, in an English-German language translation device, an English input would result in a German output. A German input would result in an English output using the same networks. The following procedure may illustrate the functioning of a Bi-Polar network. Turning now to FIG. 11 which shows the flow chart for a simple Bi-Polar network without input or output GATE.
______________________________________
Label Operation
______________________________________
START Wait for the INPUT POINTER input from a
49 previous network. This represents the input
sequence such as Question of command.
50 Load INPUT POINTER into Matrix register.
(Also load INPUT GATE and OUTPUT GATE if
required into the Matrix register).
51 Search network memory to find a memory word
which matches the INPUT POINTER. (INPUT
GATE and OUTPUT GATE) in the Matrix register.
52 If such word is located supply the OUTPUT
POINTER from that memory word to the output net-
work generator 53. The OUTPUT POINTER
represents the desired output Answer or Excecu-
tion sequence. Return the program to Label
START 54.
55 If such word is not located in the network
memory signal for human educational input
56. The desired output response is supplied
by a human teacher 57 and encoded by the output
network into a single ADDRESS number as
explained in "A Learning Network". This
ADDRESS number is then loaded into the OUTPUT
POINTER field of the Matrix register 58.
The Matrix register is stored in the next free
memory location in the network memory 59 to
create a new node. The program returns to - Label START
______________________________________
54.
The network described so far is a Bi-Polar network because it only contains two pointers. Additional pointers may be provided at which any pointer may be the input while the other pointers provide the output. PARALLEL NETWORKS The function of a parallel network is to convert a complex parallel input pattern into a single ADDRESS number. A biological example is the human eye in which a complex pattern such as a rose is converted into a single firing brain cell. The parallel network is distinct from the other mentioned networks in that the POINTER value is absent or implied. Each network layer has a pointer value implied by its location. Like all the other networks it will assemble itself from the supplied input data. FIG. 12 shows a three value network to illustrate the network building process. The algorithm, however, could operate with any number of values and the three value network is only an example. Each of the thirteen separate network generators operates in the same way. In a practical system there is no need to implement thirteen separate generators each with its own network memory such as in FIG. 4. A single physical network generator could execute each of the thirteen networks in sequence and store all thirteen networks in a shared mass memory such as shown in FIG. 5. The three input lines to each network generator each supply a separate ADDRESS number input. This ADDRESS number was derived in the previous layer of networks or from input sensors. The network building process stores these three input numbers as nodes in the network memory in such a way that each node contains a unique pattern. The network will expand automatically to accommodate new input pattern in a ripple through fashion so that every input pattern will result in a single ADDRESS output number. Turning now to FIG. 13 which shows the algorithm to generate a single parallel network.
______________________________________
Label Operation
______________________________________
START Wait for the three input numnbers from the
60 previous networks and buffer them in the
MATRIX REGISTER 61.
62 Search the network memory to find a location
in which the three input numbers are already
stored.
63 If such a pattern is found supply the memory
ADDRESS at which it was found as output
to the next network layer 64. The program
branch back to Label START 65.
If such a pattern is not found (66) store
the three input numbers in the next free
memory location and supply that memory
ADDRESS as output to the next layer 67.
The program branch back to Label START 65.
______________________________________
Like the previously described learning network the knowledge stored in a parallel network may be fully retrieved from the output ADDRESS number. By supplying the ADDRESS number as input to a network the original three input GATE patterns are retrieved by simply fetching the word from the supplied ADDRESS location. The parallel network may be used for the automatic assembly of artificial sense organs such as eye or touch. AN UNFOLDING NETWORK This fourth so far discovered variation of the infinite dimensional network is mentioned only for reference. In this network each node (ADDRESS) will split into a pre-determined number of copies whose function is determined by its surrounding conditions (GATE). An example is the human body which will unfold from a single fertilized cell. Each cell (node) will split into two other cells (branches) which function is determined by it immediate surrounding (neighboring cell surfaces, hormones) as GATE and its developmental state (dimension, pointer). A single cell will therefore unfold into a multitude of other cells by an automatic pre-learned process (genes). A SORTING, CRYPTOGRAPHIC AND DATA COMPRESSION DEVICE This device is illustrated in FIG. 14. This device consists of a single network generated by a circuit such as shown in FIG. 4 or FIG. 5. The network is used to learn a multitude of input patterns such as written words. It converts every input pattern into a single ADDRESS number regardless of its complexity or length. The network will expand automatically to absorb new not previously learned data sequences. The procedure is identical as described under "A Learning Network". The single ADDRESS number derived from the network generator is used in this practical system. The ADDRESS numbers are used later to retrieve the original pattern as described under "Word Retrieval from a Learning Network". To facilitate operation, a multitude of input patterns is first learned by the network. This may be done by typing in some written test from a typewriter. Every new word is absorbed by the network which will expand as required. This process may for example be accomplished by typing in some random written text such as a novel or a dictionary. The same may be accomplished by connecting the network generator to a telegraph line which normally carried written text such as telegrams. The network will absorb new patterns very rapidly at first but will slow its learning as more and more patterns are supplied more than once. At a sufficient interval of time most data patterns will be contained in the network. The network may, for example, contain most words in the English language and expand only very rarely to absorb new words. A complete vocabulary is not required for this application since missing words may be made-up by word fragments. The learning of new patterns would be disabled after the original eduction in most of the following applications. A network prepared in such a way will provide a single output ADDRESS number for each input data pattern. The ADDRESS number may later be used to retrieve the original data sequence. Such a device has three features which are very useful for practical devices. (1) Every previously learned data pattern is recognized but never stored again. This feature may be utilized to merge files such as customer lists in which each unique entry is stored just once. Another useful device could be a teaching device to teach correct typing. A word not previously learned would presumably be misspelled and cause an alarm. This feature would cause the recognition of previously stored patterns and filter out alien patterns. This may be used for security access control or the filtering of patterns such as earthquake waves or hearbeats to detect desired patterns and reject undesired patterns. (2) Every network is internally unique and depends on the sequence of its original education. The sequence in which patterns are learned is arbitrary for each network. It may, therefore, be assumed that any two networks prepared by two different persons would not be identical since words would not be learned in the same sequence. The ADDRESS output number representing the input pattern would be different for each network. If, for example, a written communication would be confidential and an intercepted message would be almost impossible to decode. A confidential ADDRESS number communication can, however, be easily decoded into its original test by an authorized person in possession of an identical network. A network may be copied into an identical network by a memory dump from the original network. An automatic encryptographic device is herewith provided. (3) Every input pattern is converted to a single ADDRESS number regardless of the length or complexity of the pattern. The ADDRESS number may then be used to retrieve the entire input pattern. The ADDRESS number may therefore be seen as representing the input pattern in highly compressed form. If a text file consisting of written English words, for example, would be converted into ADDRESS numbers before storage or transmission over long distances, a large savings in storage or transmission cost could be realized. The original text may be retrieved later without any sacrifice in accuracy. The following procedure may be used to explain the functioning of the devices.
______________________________________
Label Operation
______________________________________
EDUCATION Educate the device with an adequate number
of input patterns by a process described by
"A Learning Network".
Disable the learning of additional patterns
by software or hardware means.
START Wait for input pattern sequence.
68 Convert input pattern sequence into a single
ADDRESS number by a process described by
"A Learning Network" but without additional
storage.
69 If entire input sequence is contained in
memory supply the ADDRESS number as output
of the device.
If the input sequence is not contained in the
memory and new nodes would be required if
storage were not disabled do the following
according to the application.
Sound warning (misspelled word, alien pattern).
Go back to Label START.
Supply last recognized ADDRESS number as
output and go back to Label START (The
missing pattern is made-up by word fragments)
RETRIEVAL Wait for ADDRESS number input.
70
71 Re-generate original input pattern from
ADDRESS number by a process described by
"Word Retrieval from a Learning Network".
Go back to Label RETRIEVAL.
______________________________________
A PATTERN TRANSLATION DEVICE A pattern translation device such as shown in FIG. 15 could be designed with hardware such as shown in FIGS. 4 and 5. It is useful for converting a complex input pattern sequence into a pre-learned output pattern sequence. Its application could be for word-for-word language translation or code conversion systems. It could also be used to store and accumulate any kind of knowledge such as giving pre-learned answers to pre-learned questions. Turning now to FIG. 15 for a description of the functioning of this device. An input such as a question or a command pattern is supplied to the system 72 such as from a typewriter. A learning network generator 73 will convert the complex input pattern into a single ADDRESS number 74 in a process described under "A Learning Network". This ADDRESS number 74 is then supplied as input to a Bi-polar Network generator 75 which will supply an output ADDRESS number 76 if the output (Answer, execution) was previously learned by the system. The process is as described under "Bi-Polar Networks". The output ADDRESS number 76 is then supplied as input to an output network generator 77. This generator will retrieve the entire output pattern 78 from the input ADDRESS number 76 by a process described under "Word Retrieval from a Learning Network". The output pattern 78 represents the desired pre-learned output response such as the answer to the input question. If the input ADDRESS number 74 is not located by the Bi-polar network generator 75 a human educational input is required. This is done by a human educator who will supply the desired response 78 to the original input 72 for example by typing it 79 into the output network generator 77. The output network generator 77 will convert the educational input 79 into a single ADDRESS number 80 by a process described by "A Learning Network". Note that the output network generator 77 must be able to both generate and retrieve patterns. The output ADDRESS number 80 is then supplied to the Bi-Polar network generator 75 which will create a new node as described under "Bi-Polar Networks". This system can therewith be educated with an unlimited number of pre-learned answers to pre-learned questions. Every question or answer will be learned just once so that an almost complete repertoire is assembled after sometime. Note also that the answers and questions may be taught in any random order and that repeating patterns will not be stored again. A learning system is therewith obtained which absorbs knowledge automatically without conventional programming or supervision of its internal functioning from the human operator or educator. The system may be copied into an identical system by a conventional "memory dump". An interesting variation is the "knowledge dump" which consists of translating the nodes in the Bi-Polar network generator 75 backward through both the input network 81 and the output network 76. This should result in a dump of all the stored knowledge in a clear text format (written text) both for input 82 and output 78. Several of those "knowledge dump" copies from separate systems educated by separate human teachers could be merged into a single system by a process similar but automated as described for the education of this system. The system would reject all redundant education and expand only for new not previously learned inputs. The system memory requirement would expand only moderately but would be ultimately more "knowledgeable" than any of its human teachers. The storage, accumulation and merging of all human knowledge in unlimited reliable computers with easy access is seen as the major objective of this invention. The described system can be fully symmetrical by exchanging input with output network function. Each of the separate networks could store ore retrieve patterns in any order. A LANGUAGE TRANSLATION DEVICE This device as illustrated in FIG. 16 would function identically to the system described in "A Pattern Translation Device". The only variance consists of two additional network generators 83, 84 located in front and back of the Bi-polar network generator. The function of those two networks is to accept the ADDRESS number inputs 85 like input codes and convert them into a single output ADDRESS number 86 according to the operation described in "A Learning Network". The function may be seen if this system is used as a language translator. For example, an English sentence consisting of many words would first be converted into ADDRESS numbers one for each word. The word ADDRESS numbers 85 would then be accepted like input data by the next network 83, 84 which would convert it into a single ADDRESS number one for each complete English sentence. A further reduction in memory requirement is therewith realized. The device would be educated as described under "A Pattern Translation Device" and may be similarly copied or merged with other systems. It would function totally bi-directionally converting a pre-learned English sentence into a pre-learned German sentence and vice versa.
|
Same subclass Same class Consider this |
||||||||||