Plastic hyper-dimensional memory

Described is a plastic hyper-dimensional memory system having neuronal layers. The system includes an input layer for receiving an input and an address matrix for generating a working pre-image vector from the input. A hidden layer is included for transforming the working pre-image vector into a working vector. A data matrix transforms the working vector into a data pre-image vector. Further, the hidden layer performs neurogenesis when a novel input is detected based on the working pre-image vector, where the neurogenesis comprises adding or deleting address units. Novelty detection includes using a set of reinforcement units. Finally, an output layer generates a data vector based on the data pre-image vector.

CROSS-REFERENCE TO RELATED APPLICATIONS

This is a non-provisional patent application of 62/161,491, filed on May 14, 2015, the entirety of which is hereby incorporated by reference.

BACKGROUND OF INVENTION

(1) Field of Invention

The present invention is related to neural networks and, more particularly, to an associative neural network memory endowed with Reinforced Neurogenesis and the ability to indefinitely store new associations without forgetting previously stored information, and without saturating the memory.

(2) Description of Related Art

In machine learning, artificial neural networks are generally presented as systems of interconnected “neurons” which exchange messages between each other. The connections have weights that can be tuned based on experience, making neural nets adaptive to inputs and capable of learning. An associative neural network (ASNN) is a neural network that, using associative memory, includes a function and structure that operate similarly to the correlations in a human brain. An example of such an associative memory is the hyper-dimensional associative memory referred to as Kanerva's Sparse Distributed Memory (SDM) (see the List of Incorporated Literature References, Reference No. 1). Such an associative memory was improved upon Furber et al., in which the SDM was used to store data represented as N-of-M codes for improved storage capacity (see Literature Reference No. 2). Both the SDM and the use of N-of-M codes utilize hyper-dimensional vectors to represent data. Furber's work utilizes sparse data vectors to improve SDM storage capacity, and implements SDM as a bit-matrix representing neural connections for simplicity and high speed of the read/write algorithms. The use of N-of-M codes allows the memory to be (optionally) implemented as biologically plausible spiking neurons, and SDM in general has been identified as a hyper-dimensional model of the human cortex (see Literature Reference No. 3).

Current SDM, with or without the use of N-of-M codes, include several limitations. For example, memory is often limited to a predefined size which is unsuitable for continual storage of new data items over the lifetime of the application. Additionally, statistical correlations in the training data can overload portions of the SDM memory (local saturation) while starving others, resulting premature obsolescence of the storage medium. Further, the more items stored in memory, the worse it performs for classification of incomplete and noisy data. Importantly, there has been little research with regard to indefinite reuse of SDM memory without saturation or dynamic internal load balancing to eliminate premature memory obsolescence. Neural network research in recent decades has yet to produce a truly incremental and robust means of training new information without requiring retraining prior stored information.

Thus, a continuing need exists for an associative neural network memory endowed with the ability to indefinitely store new associations without forgetting previously stored information, and without saturating the memory.

SUMMARY OF INVENTION

Described is a plastic hyper-dimensional memory system having neuronal layers. The system includes an input layer for receiving an input (e.g., a numeric input, such as an address vector) and an address matrix for generating a working pre-image vector from the input. A hidden layer is included for transforming the working pre-image vector into a working vector. A data matrix transforms the working vector into a data pre-image vector. Further, the hidden layer performs neurogenesis when a novel input is detected based on the working pre-image vector, where the neurogenesis comprises adding or deleting address units. Novelty detection includes using a set of reinforcement units. Finally, an output layer generates a data vector based on the data pre-image vector.

In another aspect, the system includes a novelty detection algorithm, such that when an input is determined to be novel, an association between a working vector and data vector is trained to the data matrix, with a reinforcement unit tuned to recognize the association being added to the set of reinforcement units.

Further, when an input is determined to be novel, a number of address units in the hidden layer is increased.

Additionally, when the number of units in the hidden layer is increased, an address unit with a highest occupancy level is selected for replacement with two new units, such that a set of input connections to the original address unit is divided in half to form two disjoint sets of connections, and each new address unit is assigned one of the sets of connections.

Finally, the present invention also includes a computer program product and a computer implemented method. The computer program product includes computer-readable instructions stored on a non-transitory computer-readable medium that are executable by a computer having one or more processors, such that upon execution of the instructions, the one or more processors perform the operations listed herein. Alternatively, the computer implemented method includes an act of causing a computer to execute such instructions and perform the resulting operations.

DETAILED DESCRIPTION

The present invention is related to neural networks and, more particularly, to an associative neural network memory endowed with Reinforced Neurogenesis and the ability to indefinitely store new associations without forgetting previously stored information, and without saturating the memory. The following description is presented to enable one of ordinary skill in the art to make and use the invention and to incorporate it in the context of particular applications. Various modifications, as well as a variety of uses in different applications will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to a wide range of aspects. Thus, the present invention is not intended to be limited to the aspects presented, but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Before describing the invention in detail, first a list of incorporated literature references is provided. Next, a description of the various principal aspects of the present invention is provided. Subsequently, an introduction provides the reader with a general understanding of the present invention. Thereafter, specific details of various embodiment of the present invention are provided to give an understanding of the specific aspects. Finally, test results are provided to further provide specific examples and the corresponding results.

(1) LIST OF INCORPORATED LITERATURE REFERENCES

The following references are cited throughout this application. For clarity and convenience, the references are listed herein as a central resource for the reader. The following references are hereby incorporated by reference as though fully set forth herein. The references are cited in the application by referring to the corresponding literature reference number.1. P. Kanerva, Sparse Distributed Memory, MIT Press, 1988.2. S. B. Furber., G. Brown, J. Bose, J. M. Cumpstey, P. Marshall and J. L. Shapiro. Sparse Distributed Memory Using Rank-Order-Neural-Codes, IEEE Trans. On Neural Networks, vol. 18, no. 3, May 2007.3. G. R. Rinkus, A Cortical Sparse Distributed Coding Model Linking Mini- and Macrocolumn-Scale Functionality, Frontiers in Neuroanatomy, June, 2010.

(2) PRINCIPAL ASPECTS

The computer system100may include an address/data bus102that is configured to communicate information. Additionally, one or more data processing units, such as a processor104(or processors), are coupled with the address/data bus102. The processor104is configured to process information and instructions. In an aspect, the processor104is a microprocessor. Alternatively, the processor104may be a different type of processor such as a parallel processor, application-specific integrated circuit (ASIC), programmable logic array (PLA), complex programmable logic device (CPLD), or a field programmable gate array (FPGA).

This disclosure provides a Plastic Hyper-dimensional Memory system, which is a particular type of associative neural network endowed with a new algorithm of Reinforced Neurogenesis. In this aspect, neural units are created and destroyed as necessary to provide a unique capability, called Enduring Reuse; which provides the ability to indefinitely store new associations without forgetting previously stored information, and without saturating the memory. Additionally, in various embodiments, the Reinforced Neurogenesis algorithm allows the memory to dynamically balance its storage load by eliminating “overloaded” neural units that, over time, have acquired higher than average connectivity in the course of repeated storage operations. Whenever a novel stimulus is learned (stored), the most overloaded neuron is replaced by two or more “new” units that preserve a proportion of the original's input and output connections. A new type of unit, called the reinforcement unit, specific to the novel pattern may then be emplaced in order to preserve memory of the new pattern even as the memory grows indefinitely.

Various embodiments provide hyper-dimensional memory with the ability to store an ever increasing set of stored items, potentially over the lifetime of the application, without saturating the memory. The advantages may include one or more of the following:1. The ability to learn new data without forgetting previously learned information;2. Enduring ability to store new information over the lifetime of the application without saturating (overloading) the memory;3. Enduring capacity for continued adaptation in the presence of changing (non-stationary) environments and novel (or anomalous) information;4. Requires no external (tuning) parameters for its operation; and5. Memory load balancing may prevent long-term performance degradation.

The disclosure can serve any application domain requiring machine learning and recall. It may be applicable to domains such as: (1) autonomous vehicles, (2) automated robotic task planning, (3) safety systems, (4) prediction, and (5) distillation of knowledge from very large databases or high-bandwidth data-streams. The disclosure may be of particular benefit to application domains that require resilience to catastrophic failure in the presence of multi-point sensor and/or actuator failure. With its high capacity and ability to accommodate new information from a dynamic environment, the disclosure can serve complex systems such as vehicles and computer networks that can suffer from catastrophic failure mode that may arise from an innumerable array of potential combined sub-system failures.

(4) SPECIFIC DETAILS OF VARIOUS EMBODIMENTS

As noted above, this disclosure provides a Plastic Hyper-dimensional Memory system, which is a particular type of associative neural network endowed with a new algorithm of Reinforced Neurogenesis. The Plastic Hyper-Dimensoinal memory system is derived from a variation of the Sparse Distributed Memory (SDM) of Kanerva (see the List of Incorporated Literature References, Reference No. 1), which is a biologically inspired, neural network type of memory that represents human neuronal activity as bit-vectors within a hyper-dimensional space (dimension ˜10×, x at least 3). The variation utilizes sparse N-of-M codes as done by Furber et. al (see Literature Reference No. 2) to represent the neural activity of many thousands or potentially millions of units. Each code is an M-dimensional binary vector in which N of the bits are ones (representing currently active units) and the rest are zeros (inactive units). The codes are sparse in that N is much less than M, (N<<M), in order to model a neuronal system in which most units are inactive at any particular instant.

The Furber variant represents interconnections between neural units as a data matrix of binary-valued connection weights, one row of weights for each neural unit (data unit). Given a list of pairs of sparse binary vectors, each pair consisting of a prototype (the input vector) and a target (the desired output for that prototype), the matrix weights may be adjusted for each such pair using an outer-product rule (Hebbian rule). In various embodiments, for each prototype-target pair, this rule specifies that the mnthentry of the matrix is set to one when the nr component of the prototype and the mthcomponent of the target are both one. The resulting matrix is a linear function that maps the prototype vector to an output vector that is nominally equal to the corresponding target. Each such mapping is called an association and adjusting the matrix to map a particular prototype to its target is called storing an association.

Many associations can be stored in a single data matrix, although the fidelity of the output degrades as more associations are stored. This gives rise to the concepts of memory capacity (how many associations can be stored) and loading (the percentage of this number). The former is reached when ˜85-90% of the matrix weights have been changed from zero to one using the outer-product rule. Furber identifies the percentage of one-valued weights as the occupancy of the matrix. The occupancy is a key statistic exploited by this disclosure.

For the Furber variant of SDM (as shown inFIG. 3) an additional matrix, called the address matrix300, is used as a “pre-processing stage” to map the sparse address vector302into a much higher dimensional (and sparsely coded) working vector304which is then used as input to the aforementioned data matrix306. The address matrix300is determined in advance before any associations are stored; it remains fixed throughout the lifetime of the memory. Each row of the address matrix300represents an address unit which samples only N of the M input lines. Each address unit has M inputs, N of them have one-valued weights and the rest have a zero-valued weight, so that only N of the inputs are actually sampled. The set of one-valued lines is determined for each address unit randomly.

In various embodiments, the working vector304is then provided as input to the aforementioned data matrix306, and an output is computed. In this type of memory, the prototype-target pairs each consist of a nominal address vector as the prototype, and the nominal output vector (data vector) as the target. As illustrated in the figure, the address vector302(numeric inputs) is multiplied by the address matrix300resulting in the working pre-image301, which is a vector of positive values; each element is a count of how many one-valued input bits were seen at the input of a particular address unit. This produces a high-dimensional working vector304(dimension=W).

In various embodiments, a multi-winner-take all (soft-thresholding) algorithm is used to convert the working pre-image301to the sparse-coded binary working vector304. Specifically, a fixed number, w, of the largest values are selected (with ties being selected at random) and set to one, with the remainder set to zero. This produces a W-dimensional binary working vector304that is a w-of-W code. Proceeding rightward in the figure, the working vector304is multiplied by the data matrix306to produce an M-dimensional data-pre-image vector308, and soft-thresholding is use to converted it to the output (the data vector310) as a sparse N-of-M code.

Storing an association may include using a prototype to generate the working vector304, and the association between the working vector304and the data vector310is stored in the data matrix306.

An example embodiment is depicted schematically inFIG. 4, which is a hyper-dimensional memory system with reinforced neurogenesis. The hyper-dimensional memory system is based on the Furber style memory which is an SDM with three neuronal layers: (1) the input units (in the input layer400), (2) the hidden X address units (in the hidden layer402), and (3) the output data units (in the output layer404). In the work of Furber these are called respectively the address, working, and data units. The embodiment described herein augments this structure with the reinforcement units406(described in further detail below), and with neurogenesis (that occurs in the hidden layer402and as described in further detail below) which entails the addition and deletion of address units. Both these processes are triggered by a Novelty Detection algorithm (described in further detail below) during the training process. Note that the addition of an address unit increments the dimension Wand removing an address unit decrements it. However, regardless of the value of W the number w in the working code is held constant.

In various embodiments, when an input to the memory is determined to be novel, the association is trained to the data matrix, a reinforcement unit406“tuned” to recognize the specific association is added to the set of reinforcement units, and the number of address units (in the hidden layer402) is increased by a “splitting method” as described below with respect to neurogenesis.

The purpose of adding address units is to grow the memory while balancing the storage load, and the purpose of adding the reinforcement unit406is to preserve the memory of the stored association even after a large number of address units are added during subsequent storage of new associations.

In various embodiments, only the address unit having the highest occupancy is split. This keeps the memory stable, virtually eliminating the loss of previously stored items, while also expanding the capacity of the spiking neuronal memory to store new associations as needed. It also balances the memory load over time by keeping individual units from getting overloaded, which has the further benefit of distributing the load broadly across the memory. This makes the individual connections (or bits) within the memory more efficient, and preserves sparseness, thereby preserving the high-resilience to environmental inputs that are incomplete or corrupted by bit-errors.

In various embodiments and as shown inFIG. 5, when an address vector (numeric input) is presented at the memory input, the novelty detector uses the internally generated data pre-image500(depicted as element308inFIG. 3). The sum502of the pre-image components is computed and compared with a predetermined threshold504. The pre-image500is a vector (e.g., [0, 5, 0, 0, 1, 3]). Thus, the the sum of components in this example would be 0+5+0+0+1+3=9. If the sum502is less than506the threshold504, then the address vector is likely to be dissimilar to all those for which an association has been learned. As an alternative (not shown), the response of the winning reinforcement unit (see reinforcement units below) can be compared to the threshold. In other words, the sum is compared with a predetermined threshold in order to decide whether or not to add a new reinforcement unit.

In various embodiments, every address unit has input connections and output connections. The input connections (in the address matrix) are fixed and sample the input vector, the output connections (in the data matrix) are modifiable and connect into the data units. An output connection from an address unit can be considered to be an input connection from the corresponding data unit's point of view. Such a connection represents the core of the memory. Originally all such connections are initialized to zero before any training has been performed, but each can be changed to a one during training using the outer-product rule. The percentage of an address unit's output connections that have been set to one is called the unit's occupancy. The overall percentage of such connections in the entire data matrix is called the matrix occupancy, or simply occupancy.

In various embodiments, when a novel stimulus is detected during training, the address unit with the highest occupancy is selected for replacement with two new units. Occupancy refers to the number of input-output associations that a particular address unit is involved in storing. Using a “splitting method”, the set of input connections to the original unit is divided in half (using random selection) to form2disjoint sets of connections, and each new unit is assigned one them. The remainder of the connections for the new units are assigned randomly, and thereafter fixed. Similarly, each of the new units may also acquire a predetermined percentage of the original unit's output connections. However, current simulations have simply dropped the output connections of the original unit, leaving the storage provided by the new address units empty and usable for subsequent storage of new associations.

In various embodiments, the classification performance of the memory may degrade slightly due to removal of the original unit and separately due to its replacement by new units. The impact may be relatively small due to the fact that the memory is hyper-dimensional and so has thousands of address units. This may mean there is enough redundancy in the storage of the patterns that the memory is resilient to the loss of old units and the addition of new (untrained) ones. However, simulations have demonstrated that adding/removing units over time degrades performance, and a mechanism for reinforcing the memory previously stored associations is required to keep the memory functional.

In accordance with various embodiments,FIG. 6depicts a reinforcement unit406, which is added to the memory whenever a novel address vector600is presented to the memory's input during training. The address vector600is detected as being “new” by the novelty detector (shown inFIG. 5), which triggers the creation of the new reinforcement unit406with three input “ports” and a single output vector. The three input ports (address port602, working port604, and data port606) are created with fixed weights to sample only the currently active elements of the address vector302, the working vector304, and the data vector310, respectively. Whenever numeric inputs (e.g., an address vector302) is presented to the input of the memory (and received in the port602), the working304and data310vectors are calculated and placed on the reinforcement unit's ports (604and606, respectively). This results in a score for each vector in terms of how well it matches the port connections. These three scores are weighted via the weights Wa608, Ww610, and Wd612, and summed614to get an overall score.

In various embodiments, the WTA gate (for winner-take-all)616indicates that only the highest scoring reinforcement unit is allowed to send its score as an auxiliary excitation signal to the input of each of the data units (shown in the output layer404inFIG. 4). The data units that are allowed to receive this input are only those that were active when the reinforcement unit406was created. The signal boosts each unit's contribution to the pre-image data vector (depicted as element308inFIG. 3), and so enhances the probability that the corresponding bit it will be set to one when the soft-threshold309is applied.

In the simulations, various combinations of weights were used, though the value of Wa should generally be set to zero so that the memory is only sampling its internal state. In contrast, setting Wa to one and the other weights to zero gives the best performance (99-100%), but in this case the reinforcement units are acting as the memory independently of the data matrix.

In various embodiments, the splitting process has as a feature, the requirement that an address unit be deleted once it is made to split. This removes address units that are overloaded and over-expressed-preserving memory sparseness and the resilience of the response vectors. Biologically, it mimics the birth-death (life-cycle) of neural units, which may be an essential feature of human leaning and re-factoring of information learned from past experience.

(5) Simulation Test Results

To demonstrate the system, simulations were run as follows. The input and output were 512-dimensional vectors, and set to a 8-of-512 code. A set of 200 prototype-target pairs of randomly generated bit-vectors were used as “seeds” to generate the rest of the training set. Another set of prototype-target pairs was created by generating for each seed prototype the number X of new prototypes that were near to the seed (hamming distance of 4 bits), and another number Y of prototypes that were farther from the seed (hamming distance of 6 bits). The targets were generated similarly and in a corresponding fashion. Namely, when a new prototype was generated from a seed prototype, the seed's target was used as a seed to generate the new target for the new prototype using the same hamming distance from the seed target. The tests used X=0 and Y=8, resulting in a set of 1800 prototype-target pairs (data vectors).

During training, each prototype was trained to its target 40 times: The first 20 times the prototype was perturbed in 2 randomly chosen bit positions, and for the second 20 times, it was perturbed by 3 bits. Bit-vector perturbation was performed by selecting a single bit having the value one and swapping its position with a zero bit in the vector. This resulted in 40×1800=72000 training cycles.

Beginning with a population of 4096 address units, and using dynamic training (neurogenesis allowed during training) with a particular occupancy threshold (e.g., approximately 9%), the population grew to 11647 address units by the end of training. For static tests (no neurogenesis during training), the number of address units was fixed at either 4096 or at 11647, the latter number was determined by the dynamic test.

During testing, each of the 1800 prototypes was perturbed progressively to introduce from 0 to 8 bit errors using the bit-swapping process described above. For a particular number of bit errors, each prototype was perturbed by that number of bits, and then presented to the memory. The output was calculated and matched against the 1800 data vectors using the hamming distance. If the closest target was the one corresponding to the perturbed prototype, then the response was tallied as “correct”. In this way, the percentage correct over all trained prototypes was determined as a function of the number of bit errors.

If no reinforcement units are used, then the performance of the memory was determined as:1. Static with 11647 address units: approximately 85%2. Static with 4096 address units: approximately 75%3. Dynamic starting with 4096 units, ending at 11647 units: approximately 55%

The tests also show that even when a very small code is used, specifically an 8-of-512 code at the input and output, the performance of the memory was largely immune to up to 4 or 5 bit errors at the input. When the dynamic memory is endowed with reinforcement units that sample the working and data vectors, it achieves about 90% accuracy.

Two other statistics weighted the performance with respect to how recently a prototype-target pair was trained. One weighted the performance more heavily for pairs that were recently trained, and the other did to opposite. All tests showed a bias toward more recently learned pairs, but the disparity was only about 5 percentage points, and even less when using reinforcement units.

As a comparison, the above tests were performed using neurogenesis, but without the creation of reinforcement units. InFIGS. 7 and 8, the performance is shown as a function of the number of bit-errors at the input. The white bars indicate performance using neurogenesis, and the black bars indicates a static test in which the number of address units was fixed at 4096. Note that the former is much better than the latter, especially inFIG. 8which shows the case in which prototypes are generated with more cross-correlation. However, the number of prototypes storable for this level of performance is greatly reduced in comparison with the previous cases in which reinforcement units were used.