Part of Advances in Neural Information Processing Systems 12 (NIPS 1999)
Everybody "knows" that neural networks need more than a single layer of nonlinear units to compute interesting functions. We show that this is false if one employs winner-take-all as nonlinear unit:
• Any boolean function can be computed by a single k-winner-take(cid:173)
all unit applied to weighted sums of the input variables.
• Any continuous function can be approximated arbitrarily well by a single soft winner-take-all unit applied to weighted sums of the input variables.
• Only positive weights are needed in these (linear) weighted sums. This may be of interest from the point of view of neurophysiology, since only 15% of the synapses in the cortex are inhibitory. In addi(cid:173) tion it is widely believed that there are special microcircuits in the cortex that compute winner-take-all.
• Our results support the view that winner-take-all is a very useful
basic computational unit in Neural VLS!: o
it is wellknown that winner-take-all of n input variables can be computed very efficiently with 2n transistors (and a to(cid:173) tal wire length and area that is linear in n) in analog VLSI [Lazzaro et at., 1989]
o we show that winner-take-all is not just useful for special pur(cid:173) pose computations, but may serve as the only nonlinear unit for neural circuits with universal computational power
o we show that any multi-layer perceptron needs quadratically in n many gates to compute winner-take-all for n input variables, hence winner-take-all provides a substantially more powerful computational unit than a perceptron (at about the same cost of implementation in analog VLSI).
Complete proofs and further details to these results can be found in [Maass, 2000].