Neural networks, orientations of the hypercube, and algebraic threshold functions
- 1 May 1988
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 34 (3) , 523-530
- https://doi.org/10.1109/18.6032
Abstract
A class of possible generalizations of current neural networks models is described using local improvement algorithms and orientations of graphs. A notation of dynamical capacity is defined and, by computing bounds on the number of algebraic threshold functions, it is proven that for neural networks of size n and energy function of degree d, this capacity is O(n/sup d+1/). Stable states are studied, and it is shown that for the same networks the storage capacity is O(n/sup d+1/). In the case of random orientations, it is proven that the expected number of stable states is exponential. Applications to coding theory are indicated, and it is shown that usual codes can be embedded in neural networks but only at high cost. Cycles and their storage are also examined.Keywords
This publication has 20 references indexed in Scilit:
- Asymptotic normality of some Graph-Related statisticsJournal of Applied Probability, 1989
- Group actions and learning for a family of automataJournal of Computer and System Sciences, 1988
- The capacity of the Hopfield associative memoryIEEE Transactions on Information Theory, 1987
- Number of stable points for spin-glasses and neural networks of higher ordersPhysical Review Letters, 1987
- Nonlinear dynamics of artificial neural systemsAIP Conference Proceedings, 1986
- Information capacity of the Hopfield modelIEEE Transactions on Information Theory, 1985
- Optimization by Simulated AnnealingScience, 1983
- Conservative logicInternational Journal of Theoretical Physics, 1982
- Neural networks and physical systems with emergent collective computational abilities.Proceedings of the National Academy of Sciences, 1982
- Computer Solutions of the Traveling Salesman ProblemBell System Technical Journal, 1965