Patent Description:
Some neural networks are recurrent neural networks. A recurrent neural network is a neural network that receives an input sequence and generates an output sequence from the input sequence. In particular, a recurrent neural network can use some or all of the internal state of the network from a previous time step in computing an output at a current time step. An example of a recurrent neural network is a long short term (LSTM) neural network that includes one or more LSTM memory blocks. Each LSTM memory block can include one or more cells that each include an input gate, a forget gate, and an output gate that allow the cell to store previous states for the cell, e.g., for use in generating a current activation or to be provided to other components of the LSTM neural network.

<NPL>) teaches learned index structures for accessing data records.

This specification describes a system implemented as computer programs on one or more computers in one or more locations that provides a system for storing compressed data using a neural network. The system is able to encode and store data in a sparse and distributed manner in a memory to implement a learned data structure appropriate for one or more tasks. The learned data structure is highly compressive and reduces memory requirements greatly.

According to a first aspect, there is provided a system for storing compressed data using a neural network according to independent claim <NUM>.

The key data store is immutable in the sense that the key data once created is fixed and does not change over time or in use. In addition, whilst the other components of the neural network system may be learned through training, the key data is not learned.

The key data store comprises a plurality of randomly generated keys for indexing the plurality of memory locations, wherein the plurality of keys are immutable after generation.

The key data store may comprise immutable seed data for generating a plurality of immutable keys for indexing the plurality of memory locations; and the addressing system may be further configured to generate the plurality of keys based upon the seed data. By storing the seed data and generating the plurality of keys on demand rather than storing the full set of keys, memory requirements may be reduced.

It will be appreciated that using the same seed data will result in the generation of the same keys at all times. It will also be appreciated that a single seed may be used to generate a plurality of keys in addition to the possibility of one single key. For example, the seed may be used to generate a key to which an additional offset value is added to generate further keys. In another example, further keys may be generated by running a generation algorithm for multiple time steps with each time step producing a key.

The plurality of generated keys may be based upon a sample of Gaussian random variables. Where seed data is stored, the seed data comprises one or more seeds for generating the sample of Gaussian random variables. By using randomly generated keys, data may be stored at memory locations distributed throughout the memory, thereby increasing memory utilization.

The key data store may be implemented as a matrix. The keys may alternatively be known as addresses and the key data store may be known as an addressing matrix.

The addressing system may be further configured to process the key data and the query to generate a weighting associated with the plurality of memory locations based upon a similarity between the query and each of the plurality of keys. The similarity may be based upon any similarity metric such as a cosine distance or a Euclidean distance.

The system may further comprise an index of the plurality of keys based upon a k-nearest neighbor model. The similarity between the query and each of the plurality of keys may be further based upon the k-nearest neighbor model. For example, the k-nearest neighbor model may be based upon locality-sensitive hashing. In this way, the most similar keys to a query may be quickly determined. Given that the key data store is immutable, the k-nearest neighbor model need only be indexed once compared to prior art methods where the key data store is not immutable and would require re-generating the key index each time the key data store is modified.

The query neural network may be a feed-forward neural network.

The addressing system may be further configured to decorrelate the query. Processing the key data and the query to generate a weighting associated with the plurality of memory locations may be based upon the decorrelated query. In this way, training of the system to learn an appropriate query representation may be made more efficient through faster convergence. Using a decorrelated query encourages system to maximize the usage of all available memory locations for storing data, thereby avoiding selection of only a specific few memory locations for data storage. In addition, a decorrelated query may also result in better optimization during training resulting in a learned data encoding scheme that may be more compressive and hence improves upon memory usage. The decorrelation may be based upon a sphering transformation, for example, a moving average ZCA transformation. A sphering transformation may also be known as a whitening transformation.

The weighting may be based upon a sparse softmax function. That is, the function may be used to select the k-most similar keys and thus, the corresponding memory locations indexed by those keys. By selecting the k-most similar keys and corresponding memory locations, information may be shared between multiple memory locations to increase the informational content of the data stored in memory whilst also maintaining efficient memory utilization. The value of k may be selected as deemed appropriate by a person skilled in the art.

The system may further comprise an encoder neural network configured to process the input data item to generate the representation of the input data item. In this way, the representation may provide more informative features for processing than the raw input data item. The encoder neural network may be a feed-forward neural network or other suitable type of neural network for processing a particular type of input data item.

The memory read system may be further configured to generate the output memory data based upon applying the corresponding weighting associated with a memory location to the data stored at the memory location. The application of the weighting may be an elementwise multiplication. Thus, the memory read system may be a content-based soft-attention system.

The memory read system may be further configured to generate output memory data based upon the data stored at the memory locations having associated weightings greater than a threshold and to exclude data stored at other memory locations in the generation of the output memory data. The threshold may be chosen such that the k memory locations having the highest weightings are selected. The value of k may be selected as deemed appropriate by a person skilled in the art.

The system may further comprise a write word neural network configured to process the representation of the input data item to generate the received write data. In this way, the data to be written to memory may also be learned. The write word neural network may be a feed-forward neural network.

The memory write system may be further configured to generate weighted write data for each memory location based upon the corresponding weighting associated with the memory location and the received write data; and to additively write the weighted write data to each memory location. By additively writing, past data stored in the memory may be maintained. In addition, backpropagation through time over sequential writes may also be avoided. Temporal correlations may also be stored in the memory.

The system may also comprise an output representation neural network configured to process the output memory data of the memory read system, the received write data and the representation of the input data item to generate an output representation of the input data item. This enables non-linear interactions between data stored in the memory to be captured. In addition, an input data item may be modelled in part by the data stored in the memory. As the data stored in the memory may be rapidly adapted as compared to the parameters of a neural network which change slowly over time, the use an external memory as described above can enable the system to generalize where only a limited number of examples of a set of data items have been presented or where the environment or tasks are expected to change over time. Data items which belong to the same class or set may be mapped to the same memory locations thus enabling generalization of unseen data items. The output representation neural network may be a feed-forward neural network.

The system may be trained based upon a meta-learning framework. For example, the system may be trained based upon a series of tasks having a limited number of training examples in each task. The series of tasks may be sampled from a common distribution. The training dataset may comprise data that is to be stored in the memory and a set of in-distribution queries and a set of queries outside of the distribution that are representative of the data and queries that the system will likely encounter during use. It will be appreciated that the neural network system is fully differentiable and may be trained end-to-end. The system may be trained based upon a cross-entropy loss. The training targets may comprise binary classifications. The system may be trained using backpropagation jointly through a querying operation and a memory insertion operation.

The data stored in the memory may comprise data indicative of one or more sets of data. The output memory data of the memory read system may be indicative of whether the input data item belongs to a set of the one or more sets of data. For example, the system may implement a data structure similar to a Bloom filter that enables the system to rapidly determine whether an input data item belongs to a particular set of data. The neural network system may be trained to function as a Bloom filter and act as a replacement for a Bloom filter in an existing system. The system however has the capability of learning a more compressive and space-efficient data structure than a Bloom filter for a task such as approximate set membership. The system is suitable for both static and dynamic set membership tasks. In some prior art neural network systems, set data is encoded in the weights of the neural network system and is therefore not suitable for dynamic set membership tasks given the slow adaptation rate of the weights of a neural network. In the present system, the memory of the system, which is capable of rapid adaptation, is used for encoding set data and is therefore suitable for dynamic set membership tasks.

The system may further comprise a back-up Bloom filter for handling false negative results.

According to another aspect, there is provided a computer-implemented method of reading data from a neural network memory system, according to independent claim <NUM>.

According to another aspect, there is provided a computer-implemented method of writing data to a neural network memory system, according to independent claim <NUM>.

According to another aspect, there is provided a non-transitory computer readable medium according to independent claim <NUM>.

The system may be configured to receive any kind of digital data input. For example the stored data and/or input data items may comprise images (including video images), images or features that have been extracted from images; characters, words or strings, a sequence or piece of text in one or more languages e.g. text in one language and a translation of the text into another language; Internet resources (e.g., web pages), documents, or portions of documents or features extracted from Internet resources, documents, or portions of documents, content items; impression contexts for particular advertisements; features of a personalized recommendation for a user and/or features characterizing the context for the recommendation, e.g., features characterizing previous actions taken by the user; a data sequence representing a spoken utterance and/or transcript for the utterance; scores for any of the foregoing; or any other kind of data item which may be stored in a database. Generally the memory of the system may be used to store any type of data, including but not limited to the foregoing.

The subject matter described in this specification can be implemented in particular embodiments so as to realize one or more of the following advantages, the system is capable of learning a data structure appropriate to a particular task or tasks. Given that the system provides rapid adaption to new information, the system is particularly advantageous where data items can only be inspected a limited number of times, even only once, such as in a data stream. The system is also particularly advantageous in settings where tasks or an environment changes over time. The system is also capable of quickly generalizing to unseen data.

The system can learn how to effectively index and query the data structure based upon the input data, and how to effectively encode and store data in the memory. That is, the system can store information using an encoding based upon either the particular memory locations at which data is stored, or the particular data that is stored at a memory location or a combination of both where data is stored and what data is stored in the memory. The system provides greater data compression than a classical data agnostic data structure by learning to exploit the structure of the input data. As such, the system may require fewer bits per element to store data than a classical data structure. The system also provides compression across memory locations thereby achieving greater compression than other prior art memory augmented neural networks. The system therefore provides a scalable, distributed compressive write scheme.

In addition, the system is low in latency due to the architecture of the system and the efficient operations used for performing querying, addressing, and memory access.

In addition, by providing a querying mechanism and immutable key data store as described above, the size of the memory of the system may be made independent of the number of trainable parameters of the neural network components and the system may therefore be more scalable than other prior art memory augmented neural networks. Due to the independence of the size of the memory and the number of trainable parameters, the size of the memory may be modified during use even after the neural network components have been trained.

The system may implement a data structure suitable for determining approximate set membership similar to a Bloom filter or other type of data structure as appropriate.

For example, the system may be used to rapidly determine whether records exist in a large database to avoid unnecessary disk look-ups, to determine whether a data item exists in a cache, in network security to block malicious IP addresses, as a type of classifier to classify image, video, audio and text data, by an agent to determine whether a particular environment corresponds to an environment previously encountered before and how to act.

It will be appreciated that aspects can be combined and that features described in the context of one aspect can be combined with other aspects of the invention.

It will also be appreciated that components of the system such as the memory, addressing system, memory read system and memory write system may be adapted from existing memory and systems for addressing, reading to and writing from the memory comprised in existing computers. In addition, or alternatively, the components of the system may be configured to be compatible with existing memory and memory access systems and other existing computing components.

<FIG> shows an example system <NUM> for compressed data storage using a neural network. The system <NUM> is an example of a system implemented as computer programs on one or more computers in one or more locations, in which the systems, components, and techniques described below can be implemented.

The system <NUM> comprises a memory <NUM>. The memory <NUM> comprises a plurality of memory locations 101a. n configured to store data. The memory <NUM> may store any type of data as appropriate for a particular task being performed. For example, the system <NUM> may implement a data structure equivalent to a Bloom filter for performing an approximate set membership task. As such, the memory <NUM> may store data indicative of one or more sets of data. In other examples, the stored data may be image data, an encoding of the image data, or data indicative of a property associated with an image. Other modalities may also be stored such as video or audio data or text data, for example, data may relating to data in a database.

The size of the memory <NUM> may be chosen as deemed appropriate by a person skilled in the art and be chosen based upon the task being performed. As an example, for the approximate set membership task, the memory may have <NUM> to <NUM> memory locations (inclusive) with each memory location storing <NUM> to <NUM> elements (inclusive).

As described in further detail below, the system <NUM> may learn to store data in the memory <NUM> in a compressed and distributed manner such that memory requirements are greatly reduced as compared to conventional methods of storing the data.

The system <NUM> further comprises an immutable key data store <NUM> comprising key data for indexing the plurality of memory locations 101a. The key data store <NUM> is immutable in the sense that once the key data has been generated, it cannot be modified. The key data may be mapped to particular memory locations and may therefore be considered to provide an addressing mechanism for reading from and writing to the memory <NUM>. As such, the key data may also be considered to be address data. Further details with respect to the key data are described below.

The system <NUM> also comprises an addressing system <NUM> configured to process the key data and a query <NUM> to generate a weighting <NUM> associated with the plurality of memory locations 101a. The weighting <NUM> may be used in determining which of the plurality of memory locations 101a. n to access based upon a given query <NUM>. In this way, the weighting <NUM> may also be considered to be a form of address for accessing the plurality of memory locations 101a. Further details with respect to the generation of the weighting <NUM> are described below.

The system <NUM> further comprises a query neural network <NUM> configured to process a representation <NUM> of an input data item to generate the query <NUM>. The input data item may be any type of data. For example, image data, audio data, sensor data, web data and text. The representation <NUM> of the input data item may be an encoding or embedding of the input data item. For example, the representation may be a feature vector characterizing the input data item or may be a representation or encoding produced by a neural network.

The system <NUM> also comprises a memory access system configured to access memory data from the memory <NUM>. The accessing may be based upon the generated weighting <NUM> associated with the plurality of memory locations 101a. Thus, the system <NUM> may comprise a memory read system <NUM> configured to generate output memory data <NUM> based upon the generated weighting <NUM> associated with the plurality of memory locations 101a. n and the data stored at the plurality of memory locations 101a. The system <NUM> may also comprise a memory write system <NUM> configured to write received write data <NUM> to the memory <NUM> based upon the generated weighting <NUM> associated with the plurality of memory locations 101a. As noted above, the weighting <NUM> may function as a form of address to select which of the plurality of memory locations 101a. n to access. The memory access system is described in further detail below and may comprise one or more neural networks.

The system <NUM> having trainable neural network parameters can not only learn how best to encode and store data in the memory <NUM> but also how best to address and query the memory <NUM> for efficient access. As the key data is immutable and not learned, the size of the memory <NUM> is independent of the number trainable parameters and therefore improves the scalability of the system. The size of the memory may also be dynamically adjusted without the need for re-training the system.

In addition, use of a memory enables rapid adaptation to new data as compared to the parameters of a neural network which can only change slowly over time. The system can therefore generalize where only a limited number of examples of a set of data items have been presented or where the environment or tasks are expected to change over time. Data items which belong to the same class, distribution or set may be mapped to the same memory locations thus enabling generalization to unseen data items.

Referring now to <FIG>, another example system <NUM> for compressed data storage using a neural network is shown. The system <NUM> of <FIG> comprises the components of the system <NUM> of <FIG> whereby like components have the like reference numerals in the figures. In this respect, <FIG> also includes additional labels in which the memory <NUM> is labelled as "M"; the immutable key data store <NUM> is labelled as "A", the query <NUM> is labelled as "q", the weighting <NUM> is labelled as "a", the representation <NUM> of the input data item is labelled as "z", the output memory data <NUM> is labelled as "r" and the write data <NUM> is labelled as "w".

The system <NUM> further comprises an encoder neural network <NUM> configured to process an input data item <NUM> to generate the representation <NUM> of the input data item. The representation <NUM> may provide more informative features for processing and performing a required task than the raw input data item <NUM> and such a representation may be learned by training the parameters of the encoder neural network <NUM>. Training of neural network parameters is described in further detail below.

The encoder neural network <NUM> may be any type of neural network as deemed appropriate by a person skilled in the art. For example, if the input data item is an image, the encoder neural network may be a convolutional neural network or feed-forward mutli-layer perceptron (MLP). If the input data item is a sequence, such as a text sequence, video, audio sequence, the encoder neural network <NUM> may be a recurrent neural network such as an LSTM. In one example, the encoder neural network <NUM> is a three layer convolutional neural network configured to process an image input. In another example, the encoder neural network <NUM> is an LSTM with <NUM> hidden units configured to process text input such as a database row key.

The system <NUM> also comprises a write word neural network <NUM> configured to process the representation <NUM> of the input data item to generate the received write data <NUM>. In this way, the data to be written to the memory <NUM> may also be learned. Thus, the system may learn what to write to memory in addition to where to write to memory in order to further provide a distributive and compressive encoding of data for storage.

The write word neural network <NUM> may be any type of neural network such as a feed-forward MLP. In one example, the write word neural network <NUM> is an MLP with a single hidden layer of <NUM> units with a leaky ReLU non-linearity.

The system <NUM> further comprises an output representation neural network <NUM> configured to process the output memory data <NUM> read from the memory <NUM>, the received write data <NUM> and the representation <NUM> of the input data item to generate an output representation <NUM> of the input data item. The output representation <NUM> of the input data item <NUM> may be dependent on the task being performed by the system <NUM>. For example, if the task is approximate set membership, the output may be a probability that the input data item belongs to the set of input data items that has previously been seen by the system <NUM>. This may be used in applications such as caching, malicious URL detection, database querying, spell-checking amongst other applications. In another example, the task may be a classification task and the output may be a probability that the input data item, such as an image, belongs to or comprises an object of a particular class. In a further example, the output representation <NUM> may be a representation of the input data item that is a better encoding of the input data item for use in a separate system, such as a classifier or robotic agent. Thus, an input data item <NUM> may be modeled in part by the data stored in the memory <NUM>.

The output representation neural network <NUM> may be any type of neural network. In one example, the output representation neural network <NUM> is a three layer MLP with residual connections. By using an output representation neural network, non-linear interactions in the data stored in the memory can be captured.

In <FIG>, the memory read system <NUM> and the memory write system <NUM> are not specifically distinguished. It will be appreciated that components involved in reading from the memory <NUM> may form part of a memory read system <NUM> and components involved in writing to the memory <NUM> may form part of a memory write system <NUM>. It will also be appreciated that components may belong to both the memory read system <NUM> and the memory write system <NUM>.

Further details with respect to the key data will now be described. The key data may comprise a plurality of randomly generated keys for indexing the plurality of memory locations 101a. For example, the plurality of keys may be based upon a sample of Gaussian random variables. Alternatively, a different random number generation process may be used as appropriate. By using randomly generated keys, data may be stored at memory locations distributed throughout the memory, thereby increasing memory utilization.

As discussed above, after generation, the plurality of keys are immutable, that is, the plurality of keys cannot be modified after creation. Where the plurality of keys are generated randomly, the immutable key data store <NUM> may store the seed data used to generate the plurality of keys rather than the plurality of keys themselves. Therefore, the addressing system <NUM> may be configured to re-generate the plurality of keys using the immutable seed data. By storing the immutable seed data rather than the plurality of keys, the storage/memory requirements of the immutable key data store <NUM> may be reduced.

It will be appreciated that using the same seed data input to the same random generation process will result in the generation of the same keys. It will also be appreciated that a single seed may be used to generate a plurality of keys or a single key. For example, the seed may be used to generate a key to which an additional offset value is added to generate further keys. In another example, further keys may be generated by running a generation algorithm for multiple time steps with each time step producing a key.

The immutable key data store <NUM> may be implemented as a matrix. As discussed above, the key data may be considered to provide an addressing mechanism to access the memory <NUM>. As such, the key data store <NUM> may also be known as an addressing matrix.

In order to speed-up similarity comparisons between a query <NUM> and key data, the system <NUM>, <NUM> may further comprise an index of the plurality of keys. The index may be based upon a k-nearest neighbor model or an approximate k-nearest neighbor model. The k-nearest neighbor model may be based upon locality-sensitive hashing or another similarity preserving hash function. The most similar keys to a query may be found by looking-up the k-nearest neighbor model. Given that the key data store <NUM> is immutable, the k-nearest neighbor model need only be indexed once compared to prior art methods which may index the contents of the memory itself and therefore would require re-generating the index each time the memory is modified.

Referring now to <FIG>, processing for reading data from a neural network memory system will now be described. It will be appreciated that the processing may be performed using the systems <NUM>, <NUM> of <FIG> and <FIG> respectively.

At step S301, a representation <NUM> of an input data item is received. The representation <NUM> of the input data item may be generated using an encoding function as shown below: <MAT> where z is the representation <NUM> of the input data item, fenc(. ) is the encoding function and x is the input data item. As discussed above, the encoding function may be implemented using an encoder neural network <NUM>.

At step S302, the representation <NUM> of the input data item is processed by a query neural network <NUM> to generate a query <NUM>. The query neural network <NUM> may implement a function mapping a representation <NUM> to a query <NUM>: <MAT> where q is the query <NUM>, fq(. ) is the mapping function and z is the representation <NUM> of the input data item.

At step S303, key data for indexing a plurality of memory locations 101a. n of a memory <NUM> is retrieved from an immutable key data store <NUM>. The retrieval may be an accessing of the immutable key data store <NUM> to read the key data stored therein. As discussed above, the immutable key data store <NUM> may store the seed data used to generate the plurality of keys rather than the plurality of keys themselves. In this case, the retrieval of the key data may further comprise re-generating the plurality of keys using the immutable seed data. The addressing system <NUM> may be configured to perform this re-generation of the plurality of keys.

At step S304, the query <NUM> and the key data is processed by the addressing system <NUM> to generate a weighting <NUM> associated with the plurality of memory locations 101a. The weighting <NUM> may be based upon a similarity between the query <NUM> and each of the plurality of keys. For example, the similarity may be based upon a cosine distance and be implemented as: <MAT> where A is a row matrix containing the plurality of keys, qT is the query <NUM> in the form a column vector and d is a vector of similarity scores for each of the plurality of keys. Alternatively, the similarity may be based upon other type of distance such as a Euclidean distance as deemed appropriate.

The weighting <NUM> may further be based upon a sparse softmax. For example, a sparse softmax function may be applied to the similarity scores d in order to produce a probability distribution whereby only a few of the elements have a non-zero value. This may be achieved by ignoring values that are below a threshold or only selecting the top k scoring elements to have a non-zero value. Thus, a weighting <NUM> may be computed as: <MAT> where σk(. ) is a sparse softmax function and qTA is as described above.

At step S305, output memory data <NUM> from the memory <NUM> is output by the memory read system <NUM> based upon the generated weighting <NUM> associated with the plurality of memory locations 101a. n and the data stored at the plurality of memory locations. This may comprise applying the corresponding weighting <NUM> associated with a memory location to the data stored at the memory location. For example, the output memory data <NUM> may be generated as shown below: <MAT> where r is the output memory data <NUM>, M is a matrix comprising the data stored in the memory, a is the weighting <NUM> and ⊙ is an elementwise multiplication.

If the weighting <NUM> is a sparse weighting, the weighting <NUM> has an effect of selecting only a few specific memory locations to access based upon the query <NUM>. Alternatively, a threshold may be applied to the weighting <NUM> such that only the memory locations with associated weightings greater than the threshold are selected or the top k memory locations having the highest corresponding weightings may be selected. By selecting only a few specific memory locations, the system can learn to store data in the memory <NUM> in a distributed manner and information may be shared between multiple memory locations to increase the informational content of the data stored in the memory <NUM> whilst also maintaining efficient memory utilization.

If the weighting <NUM> is based upon a similarity between the key data and the query <NUM>, then the weighting <NUM> may be considered to be an attention vector for attending to specific locations in the memory <NUM> and the addressing mechanism may be considered to be a content-based soft-attention mechanism. The addressing mechanism may also be thought of as a differentiable hashing scheme.

The method may further comprise generating an output representation <NUM> of the input data item <NUM>. The generation may be based upon processing using an output representation neural network <NUM> the output memory data <NUM> read from the memory <NUM> at step S305, received write data <NUM> and the representation <NUM> of the input data item received at step S301. For example, the output representation <NUM> may be generated as shown below: <MAT> where o is the output representation <NUM>, fout(. ) is a function implemented by the output representation neural network <NUM>, r is the output memory data <NUM>, w is the received write data <NUM> and z is the representation <NUM> of the input data item.

As discussed above, the output representation <NUM> of the input data item <NUM> may be dependent on the task being performed and may, for example, be a probability score, or a final output encoding of the input data item <NUM>, or other data characterizing the input data item for use in another system.

The query <NUM> generated at step S302 may optionally undergo further processing prior to use at step S304. For example, the query <NUM> may be a vector and may undergo a decorrelation operation to decorrelate the elements of the vector. The decorrelation operation may be any appropriate type of decorrelation such as a sphering or whitening transformation. For example, the decorrelation may be based upon a moving ZCA average as shown below: <MAT> <MAT> <MAT> <MAT> <MAT> <MAT>.

In another example, the decorrelation operation may be based upon PCA. The addressing system <NUM> may be configured to perform the decorrelation. Decorrelation is particularly beneficial where a sparse and distributed addressing system is desired. Using a decorrelated query encourages the system to maximize the usage of all available memory locations in the memory <NUM>, thereby avoiding selection of only a specific few memory locations for data storage. In addition, a decorrelated query may also result in faster convergence and better optimization during training resulting in a learned data encoding scheme that may be more compressive and hence improves upon memory usage.

Referring now to <FIG>, processing for writing data to a neural network memory system will now be described. It will be appreciated that the processing may be performed using the systems <NUM>, <NUM> of <FIG> and <FIG> respectively.

Steps S401 to S404 of <FIG> are identical to steps S301 to S304 of <FIG> and therefore the above operations described with respect to steps S301 to S304 also applies to steps S401 to S404. Thus, in brief, at step S401, a representation <NUM> of an input data item is received; at step S402, the representation <NUM> of the input data item is processed by a query neural network <NUM> to generate a query <NUM>; at step S403, key data for indexing a plurality of memory locations 101a. n of a memory <NUM> is retrieved from an immutable key data store <NUM>; and at step S404, the query <NUM> and the key data is processed by an addressing system <NUM> to generate a weighting <NUM> associated with the plurality of memory locations 101a.

At step S405, write data <NUM> is received. The write data <NUM> may be generated using a write word neural network <NUM> based upon the representation <NUM> of the input data. For example, the write data <NUM> may be generated as shown below: <MAT> where w is the write data <NUM>, fw(. ) is a function implemented by the write word neural network <NUM> and z is the representation <NUM> of the input data item. Alternatively, the write data <NUM> may be received externally or may simply be the representation <NUM> of the input data item or the input data item <NUM> itself without modification.

At step S406, the received write data <NUM> is written by a memory write system <NUM> to the memory <NUM> based upon the generated weighting <NUM> associated with the plurality of memory locations 101a. This may be performed by generating weighted write data for each memory location based upon the corresponding weighting <NUM> associated with the memory location and the received write data <NUM>, and additively writing the weighted write data to each memory location. For example, the write may be performed as shown below: <MAT> where Mt+<NUM> is the memory <NUM> after writing, Mt is the memory <NUM> prior to the write, w is the received write data <NUM> and aT is the weighting <NUM>. Writing to the memory <NUM> may therefore be considered as an additive write as new data is added to the existing data in the memory <NUM>. This enables past information to be retained in the memory. It is noted that writing does not require multiplicative gating or squashing as in some prior art neural network memory systems.

The weighting <NUM> may be generated as described above with reference to <FIG>. The weighting <NUM> may be used to select which particular memory locations of the memory <NUM> to write to and therefore may be considered to be an address. The weighting <NUM> may specify that all of the plurality of memory locations 101a. n are to be written to. Alternatively, the weighting <NUM> may be sparse and specify a small subset of the memory locations to write to. In this way, data may be stored in a compressed and distributed manner across the memory locations. In addition, where the key data is randomly generated, this in combination with sparse weightings further ensures that the stored data is distributed across the memory to maximize memory utilization rather than only writing data to a few constantly used memory locations. This is in comparison to some prior art neural network memory systems that are either only capable of writing to one memory location in one time step or where multiple memory locations can be written to only very sharp addresses are chosen in practice.

It will be appreciated that whilst the above processing is presented as being carried out in a particular order, it is not intended to limit to any particular ordering of steps and the above steps may be carried out in a different order.

The neural networks of systems <NUM>, <NUM> of <FIG> and <FIG> may be trained based upon a meta-learning framework. In a meta-learning framework, training may initially be based upon sample tasks related to the task that the system is to perform before undergoing final training to adapt the system to required task. This is beneficial where there is limited training data available for the required task but other training data may be available. As such, the systems <NUM>, <NUM> may be trained with limited training data such as in few-shot or one-shot learning settings. For example, it is possible that data is provided as an ephemeral data stream whereby each data item is seen only once and must be learned based observing that single instance.

The systems <NUM>, <NUM> may implement a Bloom filter-like data structure for the task of approximate set membership. Such a system may be trained using a training dataset comprising a distribution of different sets of data with each set of data corresponding to a different set membership task. Upon each iteration of training, one of the sets of data is chosen and the data comprising the set is input to the system <NUM>, <NUM> for storage as described above. Sample data queries are generated and provided as input to the system <NUM>, <NUM>. For each query, the system provides an output to indicate whether the query data is part of the set of data that was input to the system <NUM>, <NUM>.

The system may then be trained based upon a cross-entropy loss function. For example, the loss function may take the form: <MAT> where L is the loss, j is an index over the query data, t is the number of queries, yj = <NUM> if the query data is in the set or <NUM> if the query data is not in the set, oj is the output of the system <NUM>, <NUM> and may be computed as shown in equation (<NUM>).

The parameters of the neural networks of the system <NUM>, <NUM> may then be updated using stochastic gradient descent by computing the gradient of the loss with respect to the parameters of the neural networks and backpropagating through the queries and writes performed. It will be appreciated that the neural network system described above is fully differentiable and is trainable end-to-end.

Further iterations of training may be carried out until suitable stopping criterion is reached, for example, when a maximum number of training iterations is reached. The trained system may then be further trained on the real task data. It is possible that the system may only have one opportunity to observe a particular data item and learn that it is part of the set of data. This is compared to prior art methods which may have unlimited access to the real task data and learns to model the set of data by conventional means of iterating through the entirety of the task data many times until satisfactory performance is obtained before being put to use.

As discussed above, the key data is not learned. The system may be initialized with key data prior to the start of training and remains fixed throughout the training process and in use.

Where the system uses an additive write, backpropagation through time over sequential writes may be avoided. The addition operator is commutative and as such, is invariant to the ordering of writes to the memory and the computation of gradients may be performed in parallel. As such, the system can be trained more efficiently and is scalable whereby prior art neural network systems with memory may fail to train or train poorly if backpropagation through time over very long sequences is required.

The system <NUM>, <NUM> may be used a replacement for a Bloom filter. However, a Bloom filter guarantees that no false negatives are generated. That is, given a query data item, if it the query data item is not in the set, the Bloom filter is guaranteed not to wrongly output that the query data item is in the set. The system <NUM>, <NUM> is not able to guarantee that no false negatives are generated and as such, a back-up Bloom filter may be used for storing false negatives emitted during training. Table <NUM> shows a comparison of the space requirements for a database task of storing <NUM> row-key strings for a target false positive rate between an exemplary implementation of the system (labeled as "Neural Bloom Filter") and a conventional Bloom filter and cuckoo filter.

Table <NUM> shows that even when a back-up Bloom filter is required, the combined space requirement of the memory <NUM> of the system and the back-up Bloom filter is significantly less than the space requirement of a conventional Bloom filter or cuckoo filter for storing the whole data. Thus the system has the capability of learning a more compressive and space-efficient data structure than conventional data structures. The system is capable of learning to exploit the structure in the input data distribution to provide an encoding of data that is significantly more compact than conventional data structures.

The system <NUM>, <NUM> may be used for static and dynamic set membership tasks. In some prior art neural network systems, set membership is encoded in the weights of one or more neural networks and therefore is not suitable for dynamic set membership tasks given the slow adaptation rate of the weights of a neural. The memory <NUM> of the system <NUM>, <NUM> provides the system with the capability to rapidly adapt to new data and is therefore suitable for dynamic set membership tasks.

Embodiments of the subject matter described in this specification can be implemented as one or more computer programs, i.e., one or more modules of computer program instructions encoded on a tangible non transitory program carrier for execution by, or to control the operation of, data processing apparatus. The computer storage medium is not, however, a propagated signal.

The elements of a computer are a central processing unit for performing or executing instructions and one or more memory devices for storing instructions and data.

Claim 1:
A system (<NUM>) for compressed data storage using a neural network comprising:
a memory (<NUM>) comprising a plurality of memory locations (101a...n) configured to store data;
a query neural network (<NUM>) configured to process a representation of an input data item (<NUM>) to generate a query (<NUM>);
an immutable key data store (<NUM>) comprising key data for indexing the plurality of memory locations (101a...n), wherein the key data comprises data defining a plurality of randomly generated keys for indexing the plurality of memory locations (101a...n), wherein the plurality of keys are immutable after generation;
an addressing system (<NUM>) configured to process the key data and the query (<NUM>) to generate a weighting (<NUM>) associated with the plurality of memory locations (101a...n);
a memory read system (<NUM>) configured to generate output memory data (<NUM>) from the memory (<NUM>) based upon the generated weighting (<NUM>) associated with the plurality of memory locations (101a...n) and the data stored at the plurality of memory locations (101a...n); and
a memory write system (<NUM>) configured to write received write data (<NUM>) to the memory (<NUM>) based upon the generated weighting (<NUM>) associated with the plurality of memory locations (101a...n).