Subscribe Now Subscribe Today
Research Article
 

Study on the Capacity of Hopfield Neural Networks



Humayun Karim Sulehria and Ye Zhang
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

Hopfield Neural Networks (HNNs) are an important class of neural networks that are useful in pattern recognition and the capacity is an important criterion for such a network design. In this research, we study the capacity experimentally determined by Hopfield and also highlight the upper and (lower) bounds on it. Improvements in the capacity are also determined as well as the methods for achieving the higher capacity. HNN capacity enhancements and refinements may also inspire other models.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Humayun Karim Sulehria and Ye Zhang, 2008. Study on the Capacity of Hopfield Neural Networks. Information Technology Journal, 7: 684-688.

DOI: 10.3923/itj.2008.684.688

URL: https://scialert.net/abstract/?doi=itj.2008.684.688
 

INTRODUCTION

In pattern recognition, the ability of associative memories to totally recall a pattern from a partial version of it is a useful feature. The Hopfield model of neural networks or some related models are extensively used in pattern recognition. Hopfield neural net is a single-layer, non-linear, autoassociative, discrete or continuous-time network that is easier to implement in hardware (Sulehria and Zhang, 2007a, b). The Hopfield model study affected a major revival in the field of neural networks and it has a wide range of applications.

The motivation behind an autoassociative neural network (http://scitec.uwichill.edu.bb/. access in 2007) is to mimic our natural ability to associate for example a visual image or a scent with a feeling or an event. We store away our memories with associative properties! An important feature of an associative neural network is the number of patterns that can be stored before the network begins to forget. The number of vectors that can be stored in a network is called the capacity of the network. In general, we find that (n-1) mutually orthogonal bipolar vectors, each with n elements, can always be stored using the sum of weight matrices (with diagonals set to zero).

The design specifications of high performance associative memories must have the following characteristics (Hassoun, 2002):

High capacity
Tolerance to noisy and partial inputs,
The existence of only relatively few spurious memories
Provision for a no-decision default memory/state
Fast memory retrievals

In this study, we are concerned mainly with the capacity of the HNN. As in earlier reviews by (Sulehria and Zhang, 2007a, b) we find that research on the HNN is ongoing and there are some areas of research that are being more focused. Since the HNN is easier to implement in hardware, it is natural that research on capacity study to continue as it is like increasing the efficiency of the particular model or class of neural nets. So from this point of view capacity is a most important component of HNN research.

Many researchers (Amit, 1997; Bhartikar and Mendel, 2000; Calvert and Marinov, 2000; Hammerstrom, 2003; Hopfield and Tank, 1985; Huang et al., 2005; Kakeya and Kindo, 1996; Kuh and Dickinson, 1989; Mazza, 1997; McEliece et al., 1987; Meireles et al., 2003; Shen and Wang, 2004; Sun et al., 1995; Šíma, 2001; Young et al., 1997) have worked at the HNN especially to study and try to enhance the capacity. Upper (Venkatesh, 1986) and lower (Hassoun, 2002) bounds of the capacity have been found. Some researchers (Hassoun, 2002; Kakeya and Kindo, 1996) have found that the capacity feature can be increased by using above-mentioned methods or different combinations of the methods specified herein.

CAPACITY OF THE HNN MODEL

Capacity has been called several names according to context and/or area of application of the HNN such as storage capacity, saturation level of HNN (Amit, 1997), memory capacity (Kakeya and Kindo, 1997), information capacity (Kuh and Dickinson, 1989), epsilon capacity (Venkatesh, 1986), etc. Although all these appear different on study, but when we look at the definition below one can find relation among these or maybe their similarity.

Definitions: The capacity described by De Wilde (1997) of a neural network is the number of fundamental memories it can have. Suppose a user wants to store m fundamental memories

Image for - Study on the Capacity of Hopfield Neural Networks
(1)

The i-th component of fundamental memory xα will be denoted by. The following recipe for the synaptic matrix T was proposed by Hopfield and Tank (1985):

Image for - Study on the Capacity of Hopfield Neural Networks
(2)

Where:
i = 1,...,n,
j = 1,...,n.

We call a network with this choice of weights, a Hopfield net. If we use this recipe, the capacity C1 is of the order of

Image for - Study on the Capacity of Hopfield Neural Networks
(3)

where, O means the following:

Image for - Study on the Capacity of Hopfield Neural Networks
(4)

if there exists a number n1 such that for all n > n1, f(n) = g(n). For many practical applications, n1 can be around 30.
But if T is arbitrary, with zero diagonal, for another capacity C2,

Image for - Study on the Capacity of Hopfield Neural Networks
(5)

So, capacity is a subtle concept and we will have to define it carefully. As defined in the earlier section, the number of orthogonal bipolar vectors that can be stored in a network is called the capacity of the network. One definition by Venkatesh (1986) says if we keep the error within bounds, there is a limit to the number of patterns that can be stored in the HNN. Some examples are given below in order to illustrate the capacity better.

Example 1: Lippmann (1987) gives an example of the capacity needed for the net used as a pattern classifier, that if we build a neural network for 10 classes it might require more than 70 nodes and more than roughly 5000 connection weights.

Table 1: Node estimates with application De Wilde (1997)
Image for - Study on the Capacity of Hopfield Neural Networks

Example 2: Pao (1989) illustrates with an example that for the case of an NN of 100 nodes, n = 100, the ordinary Hebbian model, that is, single-correlation model can store about 5 patterns which increases to about 500 for triple-correlation model of HNN.

Example 3: http://scitec.uwichill.edu.bb/. access in (2007) presents an example of a 4 neuron model, that can store and recall 3 patterns without error, also that if some element is missing still the net recalls without any fault. The examples show that according to different definitions we can have different levels of memory capacity (Table 1).

BOUNDS ON THE CAPACITY

As in every scientific research or mathematical model, we try to find the bounds on a function to define a region of stability, the bounds for the capacity of the HNN are recorded in this section. The bounds or limits on the capacity are shown in Table 2.

Lower bound: We begin by checking the lower bound of the capacity, if we say it is nil we get a network that sits idle doing nothing. As evidenced in Hassoun (2002) by the author that for HNN we have a lower bound on the capacity of 0.1. This is due to the fact that below the value of 0.1, spurious states exist that are the mixtures of the fundamental memories. Above this value the spurious states disappear. The lower bound is not affected by the change of definition of capacity to that which tolerates some level of error.

Upper bound: Next we move onto the upper bounds on the capacity. The maximum number of memories that may be stored in a Hopfield network is a current research topic described by Wasserman (1989) and is still under research (Šíma, 2001).

As a network of N neurons can have as many as 2N states, researchers were surprised to find that the maximum capacity was much less than this. If too many memories are stored, the network will not stabilize on some of them. Furthermore, it can remember things it has not among the desired vectors. These characteristics perplexed early researchers, who had no mathematical way to determine how many memories could be stored without encountering the problems.

Recent research has cast much light on this matter. For example, it had been conjectured that the maximum number of memories K that can be stored in a network of N neurons and recalled without error is less than cN2, where c is a positive constant greater than one. While this limit is approached in some cases, in general it proved to be excessively optimistic.

Hopfield and Tank (1985) showed experimentally that the limit was actually more like 0.15N. Wasserman (1989) cites Abu-Mustafa and St. Jacques (1985) who have shown that the number of such states cannot exceed N, a result that is compatible with observations of actual systems and is as good an estimate as was available at the time. This limit is for perfect recall of stored memories.

Rule of thumb: As a general Rule of the Thumb (ROT) in De Wilde (1997), do not try to learn more patterns than 0.13 times the number of neurons. For the sake of engineering a neural network this rule looks quite in order, but from pure mathematical point of view we try to establish a(n) upper bound(s) before saturation sets in.

In McEliece et al. (1987) we find that, for n binary-valued nodes, the number of stored patterns that can be recovered exactly can be no more than n/(4 log n) asymptotically as n approaches infinity, but if some errors are tolerable the capacity value is double at n/(2 log n).

In Venkatesh (1986), we find an upper bound of 2n. In his research it is required that asymptotically as n → ∞, for almost all choices of m fundamental memories with m < capacity, there exist some neural networks in which the chosen m-set of vectors can be stored as memories.

Table 2: Bounds on Capacity of the HNN
Image for - Study on the Capacity of Hopfield Neural Networks

This leads to the upper bound of 2n, or more appropriately the maximum upper capacity lies between 2n and 2n/1-2ε. So we find that the lower bound is 0.1n while the upper bound is n for perfect recall and 2n for recall with errors.

IMPROVEMENTS IN THE CAPACITY

Hopfield and Tank (1985) had introduced an idea of improving the storage capacity. They proposed an unlearning or Forgetting Memory (FM) idea to increase the memory capacity of the HNN model. It was studied for a net having a capacity of 0.25. The findings are shown in the Table 3.

In Amit (1997), confined his study to an exact solution within the Replica Symmetry (RS) theory. Subject to this restriction the value α = 0.138 was obtained, in remarkable agreement with Hopfield`s extrapolations from early simulations on small systems, α = 0.15. With Crisanti (1986) showed that beyond α = 0.138 the only retrieval states are found with broken replica symmetry (BRS). At α = 0.144 they found such a case where the number of errors decreases from 1.5 to 0.9%. Beyond this the error increases to 50%. They hoped that such a domain would fill the gap of 0.138≤α≤0.145. Their simulations provided the evidence that at α = 0.14 the system has retrieval states.

In Pao (1989), describes some research on the capacity of Hopfield associative memory. In McEliece et al. (1987) we find that, for n binary-valued nodes, the number of stored patterns that can be recovered exactly can be no more than (n/(4logn)) asymptotically as n approaches infinity.

In the neural network model, however, the basic-storage element is the connection weight between neurons (synapses). As the number of connections increases, the capacity increases dramatically. For example, in the case of 100 nodes, n = 100, the ordinary Hebbian model can store about five patterns.

Pao (1989) cites Chen et al. (1986) who reported that the number increased to ~500 for a Triple-Correlation Model (TCM).

Table 3: Improvements in capacity of the hopfield neural network
Image for - Study on the Capacity of Hopfield Neural Networks

Of course, the number of connections can also be enormous. It is worth noting that the greater storage capacity obtained in this manner also can be used to provide hetero-associativity. Thus, the letters AB can be stored as one pattern and A can be used as a partial cue to recover B as well. This approach is in contrast to making the correlation matrix asymmetric or to incorporate cooperative relaxation of the energy surface with time.

Wasserman (1989) cites Peretto et al. (1986) who have also studied the question of storage capacity of multi-connected neural networks. They report a thought-provoking result; namely, within the framework of Hebb`s laws, the number of stored bits is proportional to the number of synapses. However, the proportionality factor decreases when the order of involved synaptic contact increases. They suggest that this characteristic tends to favor neural architectures with low-order synaptic connectivities. They show that memory storage can be optimized through partitioning.

In their research Kakeya and Kindo (1996) and Kindo and Kakeya (1998) describe some improvements in the memory capacity of the Hopfield Neural Networks. Kindo and Kakeya (1998) describe the improvement of the associative memory capacity based on the results of the geometrical analysis. They pursued two approaches to improving the capability of the model. One to modify the state transition equation and the other to modify the weight matrix. A typical result achieved on the state transition equation was the Partial Reverse (PR) method proposed by Morita (1993) as a method of enhancing the memory capacity. Earlier they got a value of 0.29 but upon further analysis it was lowered to 0.2 for the capacity, but Morita in 1993 had suggested a value of 0.27 based on his experiments.

A typical improvement with modification of the weight matrix gives the Sign Alternating Memorizing (SAM) method which is one of the memorizing methods proposed by Kakeya and Kindo (1996). The expected memory capacity of SAM method is expected to be twice as large as that of the normal autocorrelation associative memory. However, the real memory capacity, of which the statistical estimate is 0.23, is smaller than the expected value because the interference between the two memory spaces becomes large noise in recalling processes.

In the case of the Hysteretic Associative Network (HAN) model presented by Yanai and Sawada (1990) cited by Bhartikar and Mendel (2000) they describe the results of their experiments that depending on the hysteresis width, the capacity increases from 0.16 to 0.26. They used the method of statistical neurodynamics, a macroscopic state equation was derived and the results were compared with numerical experiments. They also experimented with single- and multi-step recalling process.

Further, in one interesting study by Ezhov and Vvedensky (1996), we find that the spurious memories are also useful. Also, concepts of Quantum Associative Memories (QAM) are being considered (Ventura and Martinez, 1998) which can have very large capacities.

CONCLUSIONS

In an earlier study, we had reasoned that the HNN is still alive and kicking. Here this study resulted that the capacity by any full name is also a focus of research by many people of wide ranging expertise. We have tried to define the HNN capacity, the bounds on it are also studied. Last but not least we study the improvements or enhancements in the network model as part of looking for the best possible percentage of patterns per number of neurons needed.

The need to study the capacity of the model arose from our endeavor to design a pattern recognition system, for the purpose of design we would have settled for the rule of thumb by De Wilde (1997) but further study revealed a lot of possibilities. Also, the study of this particular model is important as it is closely related to some other associative models, so an improvement in this model may invoke research for betterment of other models. As HNN is still around for pattern recognition solely or in combination with other models we would also utilize it.

Further, in one interesting study by Ezhov and Vvendensky (1996), we find that the spurious memories are also useful, that may also affect change in the scenario for capacity research. Last of all, the methods for capacity improvement may be applied in combination to further enhance it.

REFERENCES

1:  Abu Mustafa, Y.S. and J.M. St. Jacques, 1985. Information capacity of the Hopfield model. IEEE Trans. Inform. Technol., 31: 461-464.
CrossRef  |  Direct Link  |  

2:  Amit, D.J., 1997. Mean-field Ising model and low rates in neural networks. Progress in Statistical Physics, Proceedings of the International Conference on Statistical Physics. June 5-7, Seoul, Korea, pp: 1-10

3:  Amit, D.J., H. Gutfruend, H. Sompolinsky, 1985. Storing infinite numbers of patterns in a spin-glass model of neural networks. Phys. Rev. Lett. Am. Phys. Soc., 55: 1530-1533.
Direct Link  |  

4:  Bhartikar, S. and J.M. Mendel, 2000. The hysteretic hopfield neural network. IEEE Trans. Neural Networks, 11: 879-888.
CrossRef  |  Direct Link  |  

5:  Calvert, B.D. and C.A. Marinov, 2000. Another K-Winners-take-all analog neural network. IEEE Trans. Neural Networks, 11: 829-838.
CrossRef  |  Direct Link  |  

6:  Chen, H.H., Y.C., Lee, G.Z. Sun, H.Y. Lee, T. Maxwell and C.L. Giles, 1986. High order correlation model for associative memory. NO. 151 Proceedings of the AIP on Neural Networks for Computing, August 1986, Snowbird, Utah, pp: 86-89

7:  Crisanti, A., D.J. Amit and H. Gutfurend, 1986. Saturation level of the Hopfield model for neural networks. Europhys. Lett., 2: 337-341.
CrossRef  |  

8:  De Wilde, P., 1997. Neural Network Models: Theory and Projects. 2nd Edn. Springer-Verlag, London, pp: 11-23, 44-51

9:  Ezhov, A.A. and V.L. Vvedensky, 1996. Object generation with neural networks (When spurious memories are useful). Neural Networks, 9: 1491-1495.
CrossRef  |  Direct Link  |  

10:  Hammerstrom, D., 2003. Digital VLSI for Neural Networks. In: Handbook of Brain Theory and Neural Networks, Arbib, M.A. (Ed.). MIT Press, Cambridge, MA, pp: 349-353

11:  Hassoun, M.H., 2002. Fundamentals of Artificial Neural Networks. 1st Edn. Prentice-Hall of India, New Delhi, pp: 363-394

12:  Hopfield, J.J. and D.W. Tank, 1986. Computing with neural circuits: A model. Science, 233: 625-633.
CrossRef  |  

13:  Huang, H., D.W.C. Ho and J. Lam, 2005. Stochastic stability analysis of fuzzy Hopfield neural networks with time-varying delays. IEEE Transactions on Circuits and Systems-II: Express Briefs, 52: 251-255.
CrossRef  |  Direct Link  |  

14:  Kakeya, H. and T. Kindo, 1996. Hierarchical concept formation in associative memory composed of neuro-window elements. Neural Networks, 9: 1095-1098.
Direct Link  |  

15:  Kakeya, H. and T. Kindo, 1997. Eigenspace separation of autocorrelation memory matrices for capacity expansion. Neural Networks, 10: 833-843.
Direct Link  |  

16:  Kindo, T. and H. Kakeya, 1998. A geometrical analysis of associative memory. Neural Netw., 11: 39-51.
CrossRef  |  PubMed  |  Direct Link  |  

17:  Kuh, A. and B.W. Dickinson, 1989. Information capacity of associative memories. IEEE Trans. IT, 35: 59-68.
Direct Link  |  

18:  Lippmann, R.P., 1987. An introduction to computing with neural networks. IEEE Acoust. Speech Signal Process. Magaz., 4: 5-22.
Direct Link  |  

19:  Mazza, C., 1997. On the storage capacity of nonlinear neural networks. Neural Networks, 10: 593-597.
CrossRef  |  PubMed  |  Direct Link  |  

20:  McEliece, R.J., E.C. Posner, E.R. Rodemich and S.S. Venkatesh, 1987. The capacity of the Hopfield associative memory. IEEE Trans. IT, 33: 461-482.
CrossRef  |  Direct Link  |  

21:  Meireles, M.R.G., P.E.M. Almeida and M.G. Simones, 2003. Comprehensive review for industrial applicability of artificial neural networks. IEEE Trans. Ind. Electr., 50: 585-601.
Direct Link  |  

22:  Morita, M., 1993. Associative memory with nonmonotonic dynamics Neural Networks, 6: 115-126.
Direct Link  |  

23:  Pao, Y.H., 1989. Adaptive Pattern Recognition and Neural Networks. 1st Edn. Addison-Wesley, New York, pp: 141-167

24:  Peretto, P. and J.J. Niez, 1986. Long term memory storage capacity of multiconnected neural networks. Biological Cybernetics, 54: 53-63.
CrossRef  |  Direct Link  |  

25:  Shen, Y.J. and M.S. Wang, 2004. Fuzzy Hopfield neural network approach to the channel assignment problem Proceedings of the 1st Workshop on Positioning, Navigation and Communication (WPNC’04), March 26, 2004, Shaker Verlag, pp: 61-66

26:  Šíma, S., 2001. The computational capabilities of neural networks. In: Proceeding of the 5th International Conference on ANN and GA (ICANNGA’01), 22-25 April Prague, Czech Republic, Springer-Verlag, Vienna, pp: 22-26

27:  Sulehria, H.K. and Y. Zhang, 2007. Hopfield Neural Networks-A Survey. Proceedings of WSEAS 6th International Conference on Artificial Intelligence, Knowledge Engineering and Databases (AIKED’07), February 16-19, 2007, Corfu, Greece, pp: 125-130

28:  Sulehria, H.K. and Y. Zhang, 2007. Hopfield neural networks: Model, applications and implementations. WSEAS Trans. Comput. Res., 2: 156-159.
Direct Link  |  

29:  Sun, Y., J.G. Li and S.Y. Yu., 1995. Improvement on performance of modified Hopfield neural network for image restoration. IEEE Trans. Image Proc., 4: 688-692.
Direct Link  |  

30:  Venkatesh, S.S., 1986. Epsilon capacity of neural networks. Proceedings of the Neural Networks for Computing, April 13-16, 1986, American Institute of Physics, pp: 440-445

31:  Ventura, D. and T. Martinez, 1998. Quantum associative memory with exponential capacity Proceeding of the International Joint Conference on Neural Networks, May, 4-9, 1998, IEEE, Alaska, USA., pp: 509-513

32:  Wasserman, P.D., 1989. Neural Computing: Theory and Practice. 1st Edn. Van Nostrand Reinhold, New York, pp: 93-111

33:  Yanai, H. and Y. Sawada, 1990. Associative memory network composed of neurons with hysteretic property. Neural Networks, 3: 223-228.
CrossRef  |  Direct Link  |  

34:  Young, S.S., P.D. Scott and N.M. Nasrabadi, 1997. Object recognition using multi-layer Hopfield neural network. IEEE Trans. Image Process., 6: 357-372.
PubMed  |  Direct Link  |  

©  2022 Science Alert. All Rights Reserved