A Complexity Theory of Neural Networks

Abstract

Significant progress has been made in laying the foundations of a complexity theory of neural networks. The fundamental complexity classes have been identified and studied. The class of problems solvable by small, shallow neural networks has been found to be the same class even if (1) probabilistic behaviour (2)Multi-valued logic, and (3)analog behaviour, are allowed (subject to certain resonable technical assumptions). Neural networks can be made provably fault-tolerant by physically separating the summation units from the thresholding units. New results have also been obtained on the complexity of approximation, communication complexity, the complexity of learning from examples and counterexamples, learning with multi-valued neurons, exponential lower bounds for restricted neural networks, and fault tolerance in distributed computation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 09, 1991
Accession Number
ADA241807

Entities

People

  • Georg Schnitger
  • Ian Parberry
  • Piotr Berman

Organizations

  • Pennsylvania State University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Artificial Intelligence Computing
  • Artificial Intelligence Software
  • Computational Science
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Fault Tolerance
  • Information Processing
  • Information Science
  • Information Systems
  • Language
  • Machine Learning
  • Neural Networks
  • Probabilistic Models

Fields of Study

  • Computer science

Readers

  • Neural Network Machine Learning.
  • Operations Research
  • Theoretical Analysis.

Technology Areas

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