Subject: Article on the computational power of winner-take-all

[Wolfgang Maass]

Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

The following article is now online available :


          On the Computational Power of Winner-Take-All

                       
                       Wolfgang Maass
             Technische Universitaet Graz, Austria


Abstract:

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

* Our results support the view that winner-take-all
  is a very suitable basic computational unit in Neural VLSI:
  
  - it is wellknown that winner-take-all of n input
    variables can be computed very efficiently with 2n transistors 
    (and a total wire length and area that is linear in n ) in
    analog VLSI [Lazzaro et al., 1989]
 
  - we show that winner-take-all is not just useful for
    special purpose computations, but may serve as the only nonlinear
    unit for neural circuits with universal computational power
   
  - 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).


------------------------------------------------------------------     
The full version of this article will appear in Neural Computation.
It can be downloaded from 
http://www.tu-graz.ac.at/igi/maass/#Publications
(see publication # 113).

An extended abstract will appear in the Proceedings of NIPS 1999.