General Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results

Reference:

Jiří Šíma and Pekka Orponen. General purpose computation with neural networks: A survey of complexity theoretic results. Neural Computation, 15(12):2727–2778, December 2003.

Abstract:

We survey and summarize the existing literature on the computational aspects of neural network models, by presenting a detailed taxonomy of the various models according to their computational characteristics. The criteria of classification include e.g. the architecture of the network (feedforward vs. recurrent), time model (discrete vs. continuous), state type (binary vs. analog), weight constraints (symmetric vs. asymmetric), network size (finite nets vs. infinite families), computation type (deterministic vs. probabilistic), etc. The underlying results concerning the computational power and complexity issues of perceptron, RBF, winner-take-all, and spiking neural networks are briefly surveyed, with pointers to the relevant literature. In our survey we focus mainly on digital computation where inputs and outputs are binary in nature, although their values are quite often encoded as analog neuron states. Also we completely omit the important learning issues.

Keywords:

computational power, computational complexity, perceptrons, radial basis functions, spiking neurons, feedforward networks, recurrent networks, probabilistic computation, analog computation

Suggested BibTeX entry:

@article{SiOr03c,
    author = {Ji{\v{r}}{\'{\i}} {\v{S}}{\'{\i}}ma and Pekka Orponen},
    journal = {Neural Computation},
    month = {December},
    number = {12},
    pages = {2727--2778},
    title = {General Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results},
    volume = {15},
    year = {2003},
}