Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!s.cs.uiuc.edu!mehra
From: mehra@s.cs.uiuc.edu
Newsgroups: comp.ai.neural-nets
Subject: Re: Minimum # of internal nodes to form
Message-ID: <218600001@s.cs.uiuc.edu>
Date: 13 Oct 89 03:28:00 GMT
References: <50402@<1989Oct12>
Lines: 30
Nf-ID: #R:<1989Oct12:50402:s.cs.uiuc.edu:218600001:000:1430
Nf-From: s.cs.uiuc.edu!mehra    Oct 12 22:28:00 1989


>
>/* ---------- "Minimum # of internal nodes to form" ---------- */
>
>  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.

See Hecht-Nielson's paper in ICNN 87 proceedings.
Briefly, the argument uses Kolmogorov's theorem (1967) and Sprecher's
theorem (1972). Kolmogorov's paper solved the notorious tenth problem
of Hilbert: whether a function of several variables can be represented
as a sum of functions (possibly composite) of only one variable. The
trouble is that if we use Kolmogorov's theorem, then there is no
restriction on the form of function in each node.

Perhaps more relevant are papers of George Cybenko. He proves that a
two-layered network (having only one hidden layer) of sigmoidal units
having only a summation at the output is sufficient. However, there is
no limit on the size of the hidden layer. An important distinction
between Hecht-Nielson's and Cybenko's results is that whereas the former
talks about exact representation, the latter talks about arbitrarily
accurate approximation.

Abu-Mostafa and Eric Baum also have interesting results in this direction
but I won't get into that here.

Pankaj {Mehra@cs.uiuc.edu}