meyering@cs.utexas.edu (Jim Meyering) (12/13/90)
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.edukortge@elaine3.stanford.edu (Chris Kortge) (12/13/90)
In article <1122@ai.cs.utexas.edu> meyering@cs.utexas.edu (Jim Meyering) writes: > >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) > [...] Sontag shows that with sigmoid hidden units N-bit parity can be learned with (N+1)/2 hidden units (rounded up to the next integer). I saw this in a tech report from the Rutgers U. Dept. of Mathematics titled "On the Recognition Capabilities of Feedforward Nets". As I remember it didn't prove that this was a minimum, but it was shown to be sufficient. Chris Kortge kortge@psych.stanford.edu
meyering@cs.utexas.edu (Jim Meyering) (12/13/90)
In article <1990Dec12.211633.28627@portia.Stanford.EDU> kortge@elaine3.stanford.edu (Chris Kortge) writes:
Sontag shows that with sigmoid hidden units N-bit parity can be learned
with (N+1)/2 hidden units (rounded up to the next integer). I saw this
in a tech report from the Rutgers U. Dept. of Mathematics titled "On
the Recognition Capabilities of Feedforward Nets". As I remember it
didn't prove that this was a minimum, but it was shown to be sufficient.
Chris Kortge
kortge@psych.stanford.edu
For anyone else who's interested, I'm told there's also
E. Sontag "Sigmoids distinguish better than heavisides" Neural
Computation 1 (1989) 470-472.
--
Jim Meyering meyering@cs.utexas.edu