Maass W
Institute for Theoretical Computer Science, Technische Universität Graz, Austria.
Neural Comput. 2000 Nov;12(11):2519-35. doi: 10.1162/089976600300014827.
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 (also referred to as 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 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.
本文对采用赢家通吃计算模块的电路的计算能力展开了严谨的理论分析。尽管涉及竞争阶段的计算模型在计算复杂性理论中一直被忽视，但它们在计算脑模型、人工神经网络和模拟超大规模集成电路中被广泛使用。我们的理论分析表明，与阈值门（也称为麦卡洛克 - 皮茨神经元）和 sigmoid 门相比，赢家通吃是一个惊人强大的计算模块。我们证明了在任何由阈值门组成的前馈电路中计算赢家通吃的最优二次下界。此外，我们表明任意连续函数都可以由仅使用单个软赢家通吃门作为其唯一非线性操作的电路来近似。鉴于皮层电路中兴奋性和抑制性连接之间众所周知的不对称性，我们的理论分析还回答了神经生理学家提出的两个基本问题：如果在加权和中仅使用正权重，神经网络会损失多少计算能力；如果仅正权重具有可塑性，会损失多少自适应能力。
