Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!gem.mps.ohio-state.edu!ginosko!uunet!ncrlnk!ncr-sd!hp-sdd!ucsdhub!sdcsvax!beowulf!demers
From: demers@beowulf.ucsd.edu (David E Demers)
Newsgroups: comp.ai.neural-nets
Subject: Re: Minimum # of internal nodes to form boolean function
Message-ID: <7243@sdcsvax.UCSD.Edu>
Date: 16 Oct 89 04:40:27 GMT
References: <1989Oct12.050402.9790@boingo.med.jhu.edu> <1383@cbnewsj.ATT.COM>
Sender: nobody@sdcsvax.UCSD.Edu
Reply-To: demers@beowulf.UCSD.EDU (David E Demers)
Distribution: usa
Organization: EE/CS Dept. U.C. San Diego
Lines: 33

>In article <1989Oct12.050402.9790@boingo.med.jhu.edu> heath@cs.jhu.edu (David Heath) writes:
>>
>>  I've been told that Robert Heicht Neilson recently proved that any
>>boolean function of n inputs to n outputs can be realized with a neural
>>net having n input nodes, n output nodes and 2n-1 intermediate nodes
>>(a total of 3 layers). Is there any truth to this statement? Please
>>forgive me if this has been discussed here before.

In a paper presented at the first ICNN, Hecht-Nielsen applied
Kolmogorov's superposition theorem and showed that a result is
that any function from {0,1}^n to R^m can be represented by
m linear combinations of 2n+1 functions of the n inputs.
Unfortunately it is NOT a constructive proof.  In network terms,
you have 2n+1 hidden units, EACH WITH ITS OWN TRANSFER
FUNCTION, and no means for finding these.  And each of the m
output units has a unique function of the hidden unit activations.
The only restrictions are that the hidden unit transfer functions
must be monotonic and continuous. [see paper for more details,
Hecht-Nielsen, Kolmogorov's Mapping Neural Network Existence
Theorem, Proc. First IEEE Conf. on Neural Networks, III-11, 1987]

You might also look at Kolmogorov's paper [but you might not :-)]
Kolmogorov, On the Representation of Continuous Functions of Many
Variables by Superposition of Continuous Functions of One
Variable and Additions, Dokl. Akad. Nauk USSR, 114, 953 (1957).
There has been some other work also claiming similar result, and
I believe a better proof exists but unfortunately don't have a
cite handy.

Dave DeMers			demers@cs.ucsd.edu
Dept. of Computer Science
UCSD
La Jolla, CA  92093