Scalability in Neural Network Learning and Computation.

Abstract

Progress has been made in six topics in the area of computational complexity of neural networks. The loading problem for analog neural networks with only 6 nodes is NP-complete. Some foundational results on linear threshold functions with Boolean inputs have been extended to real- valued inputs. Hastad s lower bound on the dynamic range of weights for linear threshold functions has been improved slightly. Theoretical and experimental results have shown that Hopfield nets are inferior to classical sequential and parallel algorithms for the knight's tour problem, a special case of the Travelling Salesperson Problem. The problem of finding stable states is PLS-complete even for some very simple and restrictive classes of Hopfield nets. We have constructed n-node planar Hopfield networks that take time 2n/3 to converge sequentially, and 2n/7 to converge in parallel.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 26, 1997
Accession Number
ADA341808

Entities

People

  • Ian Parberry

Organizations

  • University of North Texas

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Application Software
  • Applied Mathematics
  • Computations
  • Computer Science
  • Computers
  • Distributed Computing
  • Dynamic Range
  • Information Processing
  • Information Systems
  • Mathematics
  • Neural Networks
  • Polynomials
  • Random Walk
  • Students

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Molecular Photonics/Laser Physics

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms
  • AI & ML - Neural Networks