Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!think.com!linus!agate!shelby!portia.stanford.edu!elaine3.stanford.edu!kortge
From: kortge@elaine3.stanford.edu (Chris Kortge)
Newsgroups: comp.ai.neural-nets
Subject: Re: min hidden units for FF parity network?
Message-ID: <1990Dec12.211633.28627@portia.Stanford.EDU>
Date: 12 Dec 90 21:16:33 GMT
References: <1122@ai.cs.utexas.edu>
Sender: news@portia.Stanford.EDU
Organization: Stanford University - AIR
Lines: 16

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