| |
Abstract:
This article initiates a rigorous theoretical analysis of the
computational power of circuits that employ modules for computing
winner-take-all. Computational models that involve competitive
stages have so far been neglected in computational complexity
theory, although they are widely used in computational brain
models, artificial neural networks, and analog VLSI. Our
theoretical analysis shows that winner-take-all is a surprisingly
powerful computational module in comparison with threshold gates (=
McCulloch-Pitts neurons) and sigmoidal gates. We prove an optimal
quadratic lower bound for computing winner-take-all in any
feedforward circuit consisting of threshold gates. Furthermore we
show that any threshold circuit consisting of two layers of
threshold gates can be simulated by a circuit that employs a single
k-winner-take-all gate as its only nonlinear operation. In addition
we show that arbitrary continuous functions can be approximated by
circuits employing a single soft winner-take-all gate as their only
nonlinear operation. Our theoretical analysis also provides answers
to two basic questions that have been raised by neurophysiologists
in view of the well-known asymmetry between excitatory and
inhibitory connections in cortical circuits: how much computational
power of neural networks is lost if only positive weights are
employed in weighted sums, and how much adaptive capability is lost
if only the positive weights are subject to plasticity. We refer to
http://www.cis.tu-graz.ac.at/igi/maass/
for further details.
|
