ECCC-Report TR00-032https://eccc.weizmann.ac.il/report/2000/032Comments and Revisions published for TR00-032en-usTue, 06 Jun 2000 13:54:39 +0300
Paper TR00-032
| On the Computational Power of Winner-Take-All |
https://eccc.weizmann.ac.il/report/2000/032In 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.
Tue, 06 Jun 2000 13:54:39 +0300https://eccc.weizmann.ac.il/report/2000/032