Related Experiment Videos
On the Circuit Complexity of Sigmoid Feedforward Neural Networks
1King's College London, London, UK
Summary
This study analyzes the circuit complexity of sigmoid neural networks, introducing new classes NN(k)(Delta) and NN(k)(Delta,epsilon). It reveals depth-size tradeoffs for implementing these networks in Boolean circuits.
Area of Science:
- Theoretical Computer Science
- Artificial Intelligence
- Circuit Complexity Theory
Background:
- Sigmoid activation feedforward artificial neural networks are analyzed.
- Existing circuit complexity classes, like NN(k), are a starting point.
- Less restrictive classes, NN(k)(Delta) and NN(k)(Delta,epsilon), are introduced for better characterization.
Purpose of the Study:
- To examine the circuit complexity of sigmoid activation feedforward neural networks.
- To compare these networks with classic Boolean and threshold gate circuit complexity classes.
- To establish relationships between newly defined and established circuit complexity classes.
Main Methods:
- Introduction of a Boolean function class F(Delta) and recursive construction of threshold gate circuits.
- Conversion of sigmoid feedforward neural networks into equivalent threshold gate circuits.
- Replacement of threshold gates with multiple-input adders, relaxing fan-in conditions.
Main Results:
- Demonstration of recursive threshold gate circuit construction for F(Delta) functions.
- Proof of inclusions among circuit complexity classes.
- Implementation of sigmoid neural networks in polynomial-size Boolean circuits with relaxed fan-in constraints.
Conclusions:
- Sigmoid activation feedforward neural networks can be implemented in polynomial-size Boolean circuits.
- Relaxing fan-in conditions allows for larger classes of sigmoid neural networks.
- Significant fan-in dependent depth-size tradeoffs exist for digital implementation.