Convergence Time Characteristics of an Associative Memory for Natural Language Processing

1 Introduction

Linear associative memories have been well studied in fields such as statistical physics [Bruce et al., 1987)[Amit, 1989][Tanaka and Yamada, 1993], and biophysics [Hop­ field, 1982; 1984] for their ability to store and recall a set of patterns robustly, even when the patterns to be re­ called can only be presented to the networks in a highly corrupted form. It is this robustness in the face of noise and an ability to recall stored patterns based on asso­ ciations that makes these memories so potentially valu­ able for natural language processing (NLP), in particular tasks which have traditionally been regarded as context driven such as word sense disambiguation.

In this paper we take a new look at one of the funda­ mental properties of a discrete time, discrete state Hop­ field network. We explore its time to convergence which has previously been investigated for the storage and re­ call of randomly generated patterns. Clearly, any pat­ terns derived from natural language sentences will not be random, but rather will reflect a complex underlying linguistic distribution. Evidence from using random, cor­ related and biased patterns suggests that the network's

*Currently Visiting Fellow at Research & Develop­ ment Center, Toshiba Corporation, 1 Komukai Toshiba-cho, Kawasaki 210 Japan. E-mail: nigel@eel.rdc.toshiba.co.jp

The knowledge which the network has about the pat­ terns to be stored is contained in the symmetric ma­ trix of weights T. Storage of the set of patterns el') (J.l = 1, .. , n) is according to the Hebb rule

which embeds the patterns as stable attractors in the network dynamics . For storage to take place two of the necessary conditions are that T should be symmetrical, thus Tij = Tj;, and that units should have zero self­ interaction, so T;; = 0.

From early numerical studies by [Hopfield, 1982] as well as analytic studies by [Amit et al., 1987a; 1987b] we know that the number of fixed points in the network's dynamics which can be associated with the patterns to be stored is limited to the storage ratio

and that a critical value exists for the storage of ran­ domly generated patterns with zero bias at O:c = 0.14. This has been observed (e.g. [Amit et al., 1987a]) to rise to 0.18 for randomly generated biased patterns. After the critical storage value is exceeded it is known that storage and recall degrade discontinuously in the large N limit [Gardner, 1986], but continuously for small N [Grensing et al., 1987] up to some point o:o (o:c < o:o).

In [Collier, 1996] it was shown that evidence existed for the shift in O:c from 0.14 to .0.18 to be extended to non-random patterns which were biased and correlated. Clearly the storage limits of the network are one funda­ mental property of this associative memory. A second fundamental property is the convergence time which we define as the time it takes to retrieve a pattern from a corrupted version of that same pattern.

This is one of Koiran et al's [Koiran, 1994] 'interest­ ing questions' for future investigation, and any evidence for an upper bound on the convergence time should be interesting across a number of fields.

3 Previous Work

Given the importance of the class of associative network models it is surprising to find that most emphasis has been placed on the storage capacity and less notice has been taken of the convergence time. Consequently there seem to be many unanswered questions which merit in­ vestigation.

Previous analysis of the time order complexity of the discrete Hopfield network for randomly generated patterns has most recently ([Tanaka and Yamada, 1993]) given us an upper bound for successful recall of O(log(N)), where N is the number of units in the net­ work. There are at least two remaining unknowns: what is the time order complexity for a failed recall, and is recall time the same for correlated , biased, non-random patterns? A secondary question relates to the factor of scale in Tanaka and Yamada's simulations which were carried out using a range of N from 100 to 10000. It would be nice to confirm their results over a range of networks to see if there are any finite size effects, as well as for those effects which come from different pattern types.

Let us first define what we mean by recall time. A re­ call will be called successful if the network converges to a stable attractor which has a vector representation V~' which is the same as a pattern in the training set dl') for all bits in the pattern. A partial recall or a failed recall will be recorded otherwise. Although other researchers have used measures such as mean cpu. time to conver­ gence, we have defined recall time to be the number of bit flips required for the network to settle into a sta­ ble state. This should provide a hardware independent measure.

In the case of the single layer Hopfield network con­ vergence to a single stable state is guaranteed, whereas in the case of multi-layered networks we would expect the network to settle into a limit cycle of length 1 or 2. In this paper we will confine our investigation to the sin­ gle layered network, but we are interested in measuring what may be termed the 'transient period' from initial network state to stability.

The great advantage of knowing that a failed recall will take much longer than a successful recall is of course a saving in processing time and a reduction in pattern recognition error. We can simply abandon a recall at­ tempt as a failure if its processing time exceeds our ex­ pectation for a network of a given size.

In an early paper [Bruce et al., 1987] report that flow times to convergence were found to depend on a number of factors the most important of which was the storage ratio o:. Of secondary importance was the system size N and the particular updating schedule.

4 Training

We train the network using the localist Hebb rule of Eqn. ( 4) to obtain the weight matrix T which encodes the knowledge about the patterns to be stored. Since artificial pattern construction would not give us the rich characteristics of natural language, the training patterns are generated from a corpus of 'real' texts. In our simu­ lations this was a corpus of English and Japanese texts taken from newspaper editorials. Each of the English content words has been sense tagged with a unique la­ bel denoting its sense. This was undertaken by finding the Japanese lexical translation of the English words in the corresponding Japanese sentence in the corpus. The resulting corpus can be considered to be sense tagged.

From this sense tagged corpus of 16000 sentences we extracted a number of subcorpora and used these as our training sets. Sentence-to-pattern construction takes place as follows: a lexicon of length N is generated for each corpus from the constituent words giving each word sense a unique index. For each sentence we generate a bit vector of length N where an occurrence of a word in the sentence is shown by the bit being set to 1 at the position the word occupies in the lexicon. The set of n patterns thus generated, ~(p) , is given to Eqn. ( 4) to generate the weight matrix T . We see that each node in the network therefore corresponds to one word in the corpus lexicon - a localist representation. Looked at another way we are generating a high dimensional symbolic feature space in which the words which constitute the sentences are the features .

This encoding, while not optimal in terms of storage capacity, does allow us to compare our results with a wealth of results from fields such as statistical physics . In terms of representational adequacy for NLP, we see that the encoding does not capture either constituency or sequential relations between words. What it does cap­ ture is simple cooccurrence in sentences between word pairs which is a minimum required in our view for the modelling of contextual knowledge of language. If this is found to be inadequate the representation could be bought closer to the ideal language model by, for exam­ ple, having a non-symmetrical weight matrix in which T;j would be interpreted as "i followed by j" and hence capturing sequence knowledge.

All of the basic parameters which define the matrices generated from each of the subcorpora TR1 to TR7 are shown in Table 1. We see that N ranges from 260 to 7045, which should show us any finite size effects and covers substantially the same range used in the simula­ tions of [Tanaka and Yamada, 1993] . We also see that the minimum value for the storage ratio a in TR1 is above the critical level ac of 0.14 predicted for unbiased random patterns. It was seen in [Collier, 1996] that this is not necessarily a problem because N is finite, thus giving us continuous degradation in storage rather than the catastrophic discontinuous effect predicted for infi­ nite N. Moreover, we also know that for biased systems of training patterns the value of the critical storage ratio ac has been observed to shift from 0.14 upwards to 0.18.

The bias constant a for each corpus of patterns is cal­ culated from the probability that a bit in a pattern will be set to 1 as follows

and then bias becomes

Giving us a value -1 :S a :S + 1. In fact, since vari­ ation between word distributions in the training corpus is quite large it is probably erroneous to try and charac­ terize patterns simply in terms of bias since individual distributions differ widely from this norm. In this re­ spect our work differs from other studies of randomly biased patterns such as [Treves and Amit, 1988][Perez­ Vicente and Amit, 1989]. For this reason we also looked at several other macro-statistics which characterise the pattern sets. These are now described and values are given in Table 1.

We calculated a simple measure of pattern correlation between patterns from Eqn. (7) as

c;(P) is the mean connectivity of the weight matrix T which is generated from training using the localist Hebb rule of Eqn. ( 4). s(P) is the fraction of the total stor­ age space N 2 which is actually used to store the word association statistics encoded through training. As the subcorpora become larger the fraction of space used be­ comes progressively smaller. We note that it shows natu­ ral language patterns generate very sparse matrices when trained with Eqn. (4).

Usually, storage of patterns which are highly biased in such an associative memory as we have described above would be difficult because of the influence of noise which leads to the destabilizing of attractor states. To compen­ sate for this noise we have introduced a global inhibitor so that where T;i = 0 according to Eqn. ( 4) we replace this with a small negative constant designed to provide the extra amount of inhibition to ensure that nominated states are attractors. The value for the inhibitor which we found best was 10/N which may well correspond to the mean number of content words in a sentence and hence the mean number of bits set to 1 in a training pattern ~~'.

Table 1 confirms that the patterns we are looking at are biased , giving us low activation networks with sparse coding. The probability of any bit being set to 1 in a training pattern is Pr(~}~'l = 1) which starts at 0.037 and decreases almost to zero in TR7 giving us a very strong bias in a throughout . We see here the influence of storing patterns representing natural language sentences because in any sentence pattern e' the mean number of content words remains fixed at about 10 irrespective of the size of the corpus. The consequence is that bias , a, is close to its limit of -1, whereas in an unbiased system we would expect it to be close to 0.

5 Simulations

In our simulations we follow the work of [Amit, 1989] and try to relate the mean perfect recall of patterns from the training set to the mean convergence rate of the network. To make the results more interesting we randomly cor­ rupt the test patterns using a level of noise mo which ranges from 0.0 to 1.0 in increments of 0.1, so that the probability of a bit in the test pattern being flipped from 1 to 0 is equal to the noise level. Noise was applied only to the 1 bits as most of the information is contained here. We can expect convergence times to increase with m0 as the number of bits which need to be reset increase.

To calculate the fraction of error in recall we have looked at the distance between the actual stable state chosen by the network V~' for a pattern {~', and the nominated stable state V~' in autoassociation tests. We can measure the fractional Hamming distance between V~' and V~' as

The mean error free fraction F I is defined as

In order to calculate F I we therefore measure the frac­ tion of error free recalls for an ensamble of test patterns taken from the training set {(I') over a large number of trials.

Convergence times were estimated from the mean number of bit flips required for the network to reach a stable state. The number of bit flips is the number of network updates which result in an output unit V; changing state from 0 to 1 or from 1 to 0. This quantity was also calculated over the same trials as noise m0 was increased from 0.0 to 1.0 in 0.1 increments.

FI and mean convergence times were estimated nu­ merically for 50 test patterns taken from the training sets TR1 to TR7 (shown in Table 1) over 10 trials. This was then repeated for each level of noise m0 . Unlike pre­ vious simulations we cannot easily 'manufacture' train­ ing patterns, so we are limited to the values of a which the corpora give us.

Results for the mean error free fraction F I given in Figure 1 show us that pattern sets with storage ratios less than 0.20 have good recall while those above this level show continuous degrading recall. As [Collier, 1996] reported, this leads us to put the critical storage ratio ac somewhere around 0.18. In this respect TR1 toTR3 have similar perforance and TR4 to TR7 show degrading performance as a increases.

Looking now at mean spin flip to convergence results in Figure 2 we see that the training sets which performed well in recall (TR1 to TR4) have similar convergence times. Clearly TR5 to TR7 take much longer on average to converge to a stable state. If we take a closer look at TR1 to TR4 in Figure 3 we see that in fact TR1 to TR3 have almost the same convergence times and TR4 is slightly greater, confirming again that TR4 has degraded performance.

This result seems to agree with [Bruce et al., 1987]'s conclusion that a is a factor in convergence times. We can say that our simulations have shown that where a ~ ac then convergence times will be governed by the amount of induced noise, m0 , and the number of 1 bits in the pattern, shown by (1-Jai)N. When o: > O:c con­ vergence will be much greater than this, as observed by [Tanaka and Yamada, 1993], and is related to both the size of the system N, the difference of the storage ra­ tio from the critical value (o:c - o:) and the amount of induced noise mo.

6 Conclusion

Estimating the convergence time order for successful and failed recall using single spin flips is an approach which is clearly limited in scope. The results need confirming analytically and also for other natural language training sets. Nevertheless our results do have something impor­ tant to say about convergence times for linear associative networks of the Hopfield type.

We have seen that the predicted convergence rate of O(log(N)) was not observed in our training sets, possi­ bly because of correlations between patterns and bias, despite using a similar range of system sizes for N as [Tanaka and Yamada, 1993]. The earlier observation by [Bruce et al., 1987] of the convergence rate being linked to the storage ratio o: was observed and appears to be the major factor. When recall fails we have more complex behaviour with convergence times being governed by a number of factors of which system size and the storage ratio are clearly dominant.

Acknowledgements

I would like to thank Professor J. Tsujii for his many helpful and critical suggestions on the computational lin­ guistic aspects of this work. I also gratefully acknowl­ edge the kind permission of Asahi Newspapers of Japan to use their editorial corpus. Funding was provided by the Economics and Social Research Council in the UK award no. R00429434065.