Generalized Connectionist Associative Memory

1 Introduction

AssoCiative Memory is an important problem, with nu­ merous applications in AI and in pattern analysis. Here we consider this problem in the setting of recurrent con­ nectionist networks. In this setting, the problem is defined as follows [Hopfield, 1982; Hertz et al., 1991; Kamp and Hasler, 1990]. Store m vectors x 1 , ... , xm, each in { 0, 1} n, in the fixed points of a recurrent neural network in such a way that

1. most if not all the vectors xP are stable, i.e. fixed points of the network.
2. the stable vectors xP have reasonably large basins of attraction around them.

A lot of work has been done on this problem [Hertz et al., 1991; Kamp and Hasler, 1990]. The problem has also been extended to store (i) real-valued vectors in [0, 1]n [Hopfield, 1984; Farrell and Michel, 1990] and (ii) vectors in {0, 1, ... , q- 1} for any integer q > 2 [Rieger, 1990; Kohring, ; Jagota et al., 1998]. These have expanded the set of applications accordingly.

In this paper we present a further extension. Here we permit a component of a vector to store not merely a scalar value but a set of values. This expands the set of associative memory applications accordingly.

One illustrative application involves storing a col­ lection of generalized consensus sequences (gsequences) that describe important signals, i.e. local regions with against this stored set. With regards to the second, the following application is demonstrated. A very large col­ lection of binary images is stored in the model by coding these images as gtuples. The model is shown to work well in removing noisy black pixels in noisy versions of stored images.

2 The Model

The model generalizes a model introduced earlier for the special case in which all gtuples are tuples (i.e. , each component of a gtuple is a singleton set) [Jagota et al. , 1998].

Let n1 and n2 be the minimum and maximum lengths of gtuples on alphabet a to be stored. Such gtuples will be called library gtuples. The model structure is described by a (partite) graph G = (V, E) whose ver­ tices represent neurons and edges their connectivity in the associated network. For convenience we describe all storage and retrieval operations on this graph; the cor­ respondence to the connectionist network is established in a separate section. The vertex set V of G will be (o: x {l, ... ,n2}) U {n1 , ... ,n2}. That is, V contains a vertex for every possible pair (alphabet-symbol, po­ sition) and for the various possible lengths n1 , . .. , n2. The edge set E of G will depend on the library gtuples t 1 , ... , tm. To describe the storage process the following notation is useful. For a given gtuple t of length n define n sets

The sets Vi ( t) are subsets of the vertex set V (G) of the graph G. Define the join Vi ( t) ~ Vi ( t) of two sets Vi(t) and Vi(t) as the set of edges joining every vertex in Vi(t) with every vertex in Vi(t).

The vertices in V (G) are partitioned into V 1 , V 2, ... , Vn 2 , { n1 , }, ... , { n2} which we will call columns. These columns induce an n2 x (n2 - n1 + I)­ partite structure on G.

During our exploratory work we found that we were able to assure that the connectionist memory had the stable storage property only under the following restric­ tion on the library gtuples. Let k = (k1 , ... , kn 2 ) de­ note an n2-tuple of fixed positive integer values. We require that component i of every library gtuple con­ tain exactly ki elements from o:. Such gtuples are called k-uniform gtuples. Though this condition is very restric­ tive, it turns out that collections of arbitrary gtuples can be stored by recoding them to k-uniform gtuples for an appropriate choice of k (see below).

We now describe the storage process. The k-uniform library gtuples are presented sequentially, once each, to the storage algorithm. Initially, before any gtuple is pre­ sented, G has zero edges. When gtuple t = tP of length n is presented, the graph G is modified as follows.

• For each unordered pair i I- j, 1 :=; i, j :=; n, the edges in the join Vi(t) ~ Vi(t) are added toG (if some are already present, they are not added).
• For each i = 1, ... ,n, edges in the join Vi(t) ~ {n} are added to G if previously absent.

We now explain how arbitrary gtuples may be re­ coded to uniform ones. Given a collection T of gtu­ ples, for each position i = 1, ... , n2, let ki denote the largest positive integer such that there. exists a gtuple in T whose ith component contains ki values from the alphabet O:i· We now expand the alphabet o:i to in­ clude ki more symbols (i, 1), ... , (i, ki)· We then recode each library gtuple as follows: whenever component j of library gtuple tP contains ni < kj values we add the values (j, 1), ... , (j, kj - nj) to this component. Under this recoding all library gtuples are now k-uniform.

From the storage rule, the structure of a stored gtuple as represented in the resulting graph G (after all the recoded gtuples have been stored) is readily apparent . This structure will lead to our definition of memory. For a given gtuple t of length n( t), define

that is, the set of vertices in G associated with t. Let G[t] denote the subgraph of G induced by V(t). If t is a library gtuple, G[t] has the following structure: for every i f::- j, Vi ( t) is joined with Vi ( t); for every i = 1, ... , n(t), Vi(t) is joined with the vertex labeled n(t). Furthermore, IVi(t)l = ki for all i. We will call this structure a k-uniform complete (n(t) + !)-partite subgraph of G.

The structure of the previous paragraph leads to the following definition of memory, parametrized by the uni­ formity vector k. We will say that a subgraph G[U] of G induced by a vertex set U ~ V (G) is a memory if and only if G[U] has the following structure:

1. U contains no more than one vertex from columns n2 + 1, n2 + 2, .... If U contains such a vertex, call it Un·
2. U contains no more than ki vertices from column i :::; n2,
3. For all pairs i I- j, 1 :::; i,j :::; n2 , columns Ui and Ui are joined. Here Ui =Vi n U.
4. For all i :=; n2 , column Ui is joined with {un}·
5. U is a maximal vertex set satisfying conditions 3 and 4 under the constraints imposed by conditions 1 and 2.

The memory definition of the previous paragraph is at­ tractive for the following reasons. First, the k-uniform complete (n(t) + 1)-partite subgraph associated with a (recoded) library gtuple t satisfies this definition. Hence every (recoded) library gtuple is stored stably in the sense that it is necessarily recorded as a memory. Second, a Hopfield-type connectionist network may be associated with our graph G in such a way that this definition co­ incides with the fixed points of such a network. One consequence of this fact is that a memory is retrievable by simple hill-climbing. In the connectionist context it is also worth noting that, by contrast with our scheme, it is impossible to store even three binary vectors stably in a binary Hopfield memory in the worst case [Dembo, 1989; Abu-Mostafa and Jacques, 1985).

Although all library gtuples are stored stably, spurious memories may develop. A spurious memory is a memory (see definition of memory given in an earlier paragraph) that is not associated with a library gtuple. It is the spu­ rious memories that interfere with associative retrieval operations of the model. A good theoretical character­ ization of how spurious memories emerge in our model (as a function of the library gtuples) appears difficult. In this paper we indirectly assess the damage caused by spurious memories in various application contexts.

2.1 Illustrative Example

We now work through an example. Consider a multiple alignment of a set of DNA sequences of identical length.

ACCCAT ACACAT CCCCGT

TCCCAT

(With some loss of information) we describe this alignment by the generalized consensus sequence ({A,C,T}, {C}, {A,C}, {C}, {A,G}, {T}).

Consider now a collection of generalized consensus se­ quences of varying length.

To store this collection in our model we first determine k = (3, 2, 2). We then recode each gsequence to make it k-uniform in the manner described earlier, and then store the resulting collection according to the storage algorithm described earlier. Figure 1 shows the graph formed after all the recoded gsequences have been stored.

2.2 Connectionist Correspondence

The graph G formed after the recoded k-uniform gtuples have been stored may be represented as a connectionist (Hopfield-type) network in such a way that there is a one­ to-one correspondence betw.een the fixed points of the network and the memories of the graph (see the graph­ structural definition of memory in a previous section). The resulting connectionist network is an extension of the one in [Jagota et al., 1998].

The neurons in the network are the vertices in G. Sym­ metric weights between pairs of neurons are added as follows.

1. Each edge in the graph is represented by a weight of 0. network.
2. Each non-edge in the graph between two vertices not in the same column is represented by a sufficiently negative weight.
3. Each pair of vertices i, j in the same column is con­ nected by a weight of -1.
4. Each pair of vertices i, j representing gtuple lengths is connected by a sufficiently negative weight.

are identical.

5.

All self-weights are 0.

Biases (constant external inputs) to neurons are as follows.

1. Each tuple-length neuron (neuron labeled n2 + 1, ... ,) has a bias of 0.5.
2. Each neuron in column i (including the expanded­ alphabet neurons in that column) has a bias of k;- 0.5.

This yields a Hopfield network with binary 0/1 neu­ rons and a symmetric, zero-diagonal weight matrix, whose fixed points are the local minima of a certain en­ ergy function [Hopfield, 1982]. The one-to-one corre­ spondence between these fixed points and the memories of the graph is easily established. The weight condition 2 ensures that in a fixed point if two neurons from dif­ ferent columns are ON, then the associated vertices are adjacent in the graph. The weight condition 3 ensures that in a fixed point at most one tuple-length neuron is ON. The bias condition 2 taken together with the weight condition 3 ensures that in a fixed point not more than k; neurons are ON in column i.

3 Results

As noted earlier, when a large number of library pat­ terns are stored, the model is not expected to work well on full retrieval of library patterns from distorted probe patterns. This is due to the compact architec­ ture and distributed storage mechanism, which leads to a low error-correction capacity [Hertz et al., 1991]. It turns out nevertheless that limited kinds of retrieval on large collections of stored library patterns is feasible. The first kind is novelty detection in which one wishes to test if a probe pattern is novel relative to the col­ lection of library patterns. The second kind is noise removal in which one wishes to filter out noise from a probe pattern obtained by adding noise to a library pat­ tern. The precursor of this model has been shown to work well on both these kinds of retrieval [Jagota, 1994; Duffy and Jagota, 1998]. Here we demonstrate that the generalized model works on these types of retrieval as well.

3.1 Novelty Detection

To demonstrate novelty detection, we picked a signifi­ cant task from Bioinformatics. We start with a dataset of 3,202 blocks, each block representing a multiple align­ ment of segments of certain proteins, assembled by [Henikoff and Henikoff, 1991]. We convert each block to a generalized consensus sequence on the twenty-letter protein alphabet. The resulting collection of 3,202 gse­ quences is stored in the model. The average length of a gsequence in this collection is 32.56; the average size of the set in a position in a gsequence is 4.2.

To assess the model's performance we distorted each library gsequence by replacing each value v in the value­ set stored at position j by a random alphabet-symbol with probability p. Figure 2 reports, as a function of p, the percent of the 3,202 probe gsequences that were detected as not in the library collection by the model. For p = 0, as expected, none of the probe gsequences was flagged as novel because all are the library pat­ terns; hence stable. The percentage of probe patterns detected as novel increased as p was increased, which demonstrates that the model works well on this task.

It turns out that the model is also able to report (an efficiently-computable) score for each probe gsequence indicating its distance from the stored library collection. The following definition of score generalizes the one in [Duffy and Jagota, 1998]. For a vertex set U = U(t) associated with a probe gsequence t define score(U) as the number of pairs of vertices in U that are in different columns and are non-adjacent divided by the number of pairs of vertices in U in different columns.

Figure 3 reports, as a function of p, the average score of the probe patterns. We see that the average score increases linearly with p. This validates the suitability of this scoring scheme.

3.2 Noise Removal

To demonstrate noise removal, we picked the following task from image processing. We stored in our model a dataset of 60,000 binary images of handwritten digits. Each image was roughly 28 x 28 pixels, with approxi­ mately 140 of them being black. To store an image in our model we coded it as a gtuple as follows. Each col­ umn of an image represented a position in the gtuple. The positions of the black pixels in column i in an image was the value-set stored in component t[i] of the associ­ ated gtuple.

As our test set, we picked 3000 of these images and dis­ torted them by converting each white pixel into a black pixel with probability 0.01. On average this added 6.4 pixels of black noise in the probe image. We then used a noise-removal algorithm in conjunction with our model that simply converts (sequentially) those black pixels to white pixels in the probe gtuple that are maximally non­ adjacent to other black pixels. We found that on average this mechanism cleaned up 3.3 of the 6.4 noisy black pix­ els in the probe.

This task may also be mapped to the original con­ nectionist model [Jagota, 1994], by treating each library image as a (28 x 28)-bit binary vector. However this has some drawbacks. The resulting network has twice as many neurons. More importantly, this coding is dense (half the neurons in the network participate in each memory). By contrast only about 1/6th of the neurons in the network (140 out of 28 x 28) participate in a mem­ ory in the generalized network.

4 Current and Future Work

One appealing feature of this model is that it may also be used to (efficiently) assign a score to a probe sequence- a type of "distance" from the entire stored library collec­ tion. This opens up some interesting application possi­ bilities, that we are now beginning to investigate.