__
TR00-032 | 31st May 2000 00:00
__

#### On the Computational Power of Winner-Take-All

TR00-032
Authors:

Publication: 6th June 2000 13:54

Downloads: 4329

Keywords:

**Abstract:**
In this paper the computational power of a new type of gate is studied:

winner-take-all gates. This work is motivated by the fact that the cost

of implementing a winner-take-all gate in analog VLSI is about the same

as that of implementing a threshold gate.

We show that winner-take-all gates have strictly larger computational

power than threshold gates in the following sense:

a threshold circuit consisting of quadratically many threshold gates is

needed to simulate a single winner-take-all gate.

Furthermore any polysize 2-layer feedforward threshold circuit with

polysize weights can be simulated by a single (!) k-winner-take-all gate

applied to polynomially many linear gates. Hence one arrives here at a

new representation of the second level of the well-known complexity

class TC_0 , which appears to be mathematically more perspicuous.

In the context of computing real valued functions one can show that

arbitrary continuous functions with values in [0,1] can be approximated

on bounded domains by circuits consisting of a single soft winner-take-all

gate applied to linear gates. One may argue that among the known types

of "universal approximators" these circuits are of the simplest mathematical

structure:

One just considers a set of linear functions L_1,..,L_n

over the real valued domain, and watches for each argument x the

rank of L_1(x) in the linear order of {L_1(x),...,L_n(x)}.

Up to a fixed scaling of this rank into the target range [0,1],

the "rank" of L_1(x) provides the desired "universal approximator"

that can be used to approximate arbitrary continuous functions.