|
NeuroCOLT
Technical Report NC-TR-99-048
On
the Computational Power of Winner-Take-All
Wolfgang Maass
Technische Universität Graz
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, arti,cial
neural networks, and analog VLSI. Our theoretical analysis shows that
winner-take-all isa 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. 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.
Download Compressed Postscript
|