Neural Computation with Winner-Take-All as the Only Nonlinear Operation

Part of Advances in Neural Information Processing Systems 12 (NIPS 1999)

Bibtex Metadata Paper


Wolfgang Maass


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].