Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!meyering
From: meyering@cs.utexas.edu (Jim Meyering)
Newsgroups: comp.ai.neural-nets
Subject: min hidden units for FF parity network?
Message-ID: <1122@ai.cs.utexas.edu>
Date: 12 Dec 90 20:02:29 GMT
Organization: U of TX at Austin CS Dept
Lines: 32


Has anyone determined the minimum number of hidden units required to
compute the parity function with a feed-forward network, learning via
backpropagation?  (assuming standard network: 3-layer, fully connected,
no shortcut connections)

In the paper "Learning Internal Representations by Error Propagation,"
Rumelhart, Hinton, and McClellan state:

    "In this architecture [a 3-layer network with full
    connections between adjacent layers and no connections
    between non-adjacent layers] it requires at least N
    hidden units to solve parity with patterns of length N."

In response to a query on the correctness of the above quote,
Dave Rumelhart wrote:

 >The statement should have read that "it requires no
 >more than N hidden units to solve the parity problem
 >with patterns of length N."

I have found solutions to the N-bit parity problem that use fewer
than N hidden units.  In particular, I have computed weights for
networks with N-1 hidden units and even for some with N-2.

Does anyone know of a proof of lower bound or of a collection of
empirical results on feed-forward nets for N-bit parity with fewer
than N hidden units?

Jim
-- 
Jim Meyering          meyering@cs.utexas.edu