The Hopfield-Clique network, associative memories, and combinatorial optimization
Arun Jagota · 1993
Much of the recent resurgence of interest in artificial neural networks dates from the seminal 1982 paper of John Hopfield, in which he developed what is now called the Hopfield Network. Much of its appeal owes not only to its analogy with well-known physical processes, but also to its close connection with practical computing devices, such as microchips. The Hopfield Network finds applications to associative memories and to combinatorial optimization, both problems of importance to Computer Science. In this thesis, we propose a special case of the Hopfield network that we call Hopfield-clique Network (HcN) and study its properties and applications. We analyze several network properties in graph-theoretic and computational complexity-theoretic settings. They include characterization of fixed points, storage properties (e.g. stable storage), dynamics (e.g. steepest descent), information capacity, and computational complexity of analyzing a network instance. We show that the network has several attractive features for associative memories, in particular its characterization of fixed points and its provision of stable storage. We apply this network to two concrete associative memory problems: (i) machine printed word recognition and (ii) error-detection under overloaded conditions. We show that the network also lends itself to heuristic solution of hard combinatorial optimization problems. We propose several optimizing dynamics and apply them to approximately solve the NP-hard problem of finding the largest clique in a given graph. We also approximately solve several other optimization problems in the network, by their reduction to the largest clique problem. Our broad contribution is in proposing and studying a special case of the Hopfield network that retains essentially all the properties of the latter, in a simpler framework which is easier to analyse. This network exhibits all facets of computation in the Hopfield network. The theoretical issues mirror those that arise in the Hopfield network--in several cases, we obtained simpler proofs of analogous or exact known results. Restricting ourselves to a special case has not restricted the practical applications. Indeed our network retains the two main applications--associative memories and optimization--of the Hopfield network.