On the circuit complexity of sigmoid feedforward neural networks

Valeriu Beiu, John G. Taylor

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

This paper aims to examine the circuit complexity of sigmoid activation feedforward artificial neural networks by placing them amongst several classic Boolean and threshold gate circuit complexity classes. The starting point is tire class NN(k) defined by Shawe-Taylor et al. (1992) Classes of feedforward neural nets and their circuit complexity. Neural Networks 5 (6), 971-977. For a better characterization, we introduce two additional classes NN(Δ)(k) and NN(Δ,ε)(k) having less restrictive conditions than NN(k) concerning fan-in and accuracy, and proceed to prove relations amongst these three classes and well established circuit complexity classes. For doing that, a particular class of Boolean functions F(Δ) is first introduced and we show how a threshold gate circuit can be recursively built for any f(Δ) belonging to F(Δ). As the G-functions (computing the carries) are f(Δ) functions, a class of solutions is obtained for threshold gate adders. We then constructively prove the inclusions amongst circuit complexity classes. This is done by converting the sigmoid feedforward artificial neural network into an equivalent threshold gale circuit (Shawe-Taylor et al., 1992). Each threshold gate is then replaced by a multiple input adder having a binary tree structure, relaxing the logarithmic fan-in condition from Shawe-Taylor et al. (1992) to (almost) polynomial. This means that larger classes of sigmoid activation feedforward neural networks can be implemented in polynomial size Boolean circuits with a small constant fan-in at the expense of a logarithmic factor increase in the number of layers. Similar results are obtained for threshold circuits, and are liked with the previous ones. The main conclusion is that there are interesting fan-in dependent depth-size tradeoffs when trying to digitally implement sigmoid activation feedforward neural networks.

Original languageEnglish
Pages (from-to)1155-1171
Number of pages17
JournalNeural Networks
Volume9
Issue number7
DOIs
Publication statusPublished - Oct 1996
Externally publishedYes

Keywords

  • Boolean circuits
  • Circuit complexity
  • Neural networks
  • Threshold gate circuits

ASJC Scopus subject areas

  • Cognitive Neuroscience
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'On the circuit complexity of sigmoid feedforward neural networks'. Together they form a unique fingerprint.

Cite this