On the computational power of winner-take-all

Area of Science:

• Computational Complexity Theory
• Computational Neuroscience
• Artificial Intelligence

Background:

• Competitive computational models, like winner-take-all (WTA), are prevalent in neural networks and brain models but under-explored in complexity theory.
• Existing computational models often use threshold gates (McCulloch-Pitts neurons) or sigmoidal gates.
• Neurophysiology highlights the excitatory-inhibitory asymmetry in cortical circuits, raising questions about computational power with restricted weight systems.

Purpose of the Study:

• To theoretically analyze the computational power of circuits utilizing winner-take-all (WTA) modules.
• To compare the power of WTA modules with traditional threshold and sigmoidal gates.
• To investigate the impact of weight restrictions (positive-only weights) on neural network computational power and plasticity.

Main Methods:

• Rigorous theoretical analysis of feedforward circuits.
• Derivation of lower bounds for computing WTA using threshold gates.
• Analysis of function approximation capabilities using soft WTA gates.

Main Results:

• An optimal quadratic lower bound is proven for computing winner-take-all in feedforward circuits of threshold gates.
• Winner-take-all is shown to be a significantly more powerful computational module than threshold or sigmoidal gates.
• Arbitrary continuous functions can be approximated using a single soft WTA gate as the sole nonlinear operation.

Conclusions:

• Winner-take-all modules offer substantial computational power, exceeding that of simpler gate types.
• The findings provide insights into the computational significance of WTA mechanisms in neural systems.
• The study addresses fundamental questions regarding computational power and plasticity under biologically plausible weight constraints.