Computing with networks of threshold elements

It is proved that all the known cases of convergence can be reduced to the case of convergence in a network operating in a serial mode, hence establishing a unified convergence theorem.

Abstract

The Hopfield model for neural networks has attracted a lot of interest in recent years mainly because it was perceived as a new idea for computing. The model can be described as a network in which every node computes a linear threshold function. The primary purpose of this thesis is to perform a rigorous analysis of the properties of this model. In particular, questions addressed are related to (i) the convergence properties, (ii) the adequacy of the model for the two applications: associative memory and computation, (iii) the relations between the model and error correcting codes and (iv) the idea of generalized networks--networks in which a single node is computing a polynomial threshold function. The network has interesting convergence properties; for example, it always converges to a stable state when operating in a serial mode. It is proved that all the known cases of convergence can be reduced to the case of convergence in a network operating in a serial mode, hence establishing a unified convergence theorem. The convergence property is the basis of potential applications of the model such as associative memory devices and computational models. The adequacy of the model for the two applications is analyzed. It is shown that the network is very limited in performance as an associative memory and is not adequate for solving hard problems. On the positive side the relations between the model and error-correcting codes are investigated. It is shown that the Maximum Likelihood Decoding problem of linear block codes is equivalent to finding the global maximum of a neural network. The dual result is also obtained: given a linear block code, a network can be constructed such that every stable state in the network corresponds to a codeword and every codeword corresponds to a stable state, thus, solving the programming problem for linear block codes. One of the main reasons for the poor performance of a network of linear threshold elements is the fact that a single node is too simple to compute much. A common solution to this problem is to consider generalized networks in which every node computes a polynomial threshold function. To evaluate the idea of generalized networks the following fundamental question is addressed: what is the power of a Polynomial Threshold (PT) element with respect to Linear Threshold (LT) elements? The answer is that not much is gained by using PT's instead of LT's. A small depth-2 circuit of LT's can compute more than a single PT element. The key for answering this question is a development of a novel lower bound technique that is based on Harmonic Analysis.