dave@boingo.med.jhu.edu (David Heath) (10/12/89)
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. -------------------------------- Dave Heath heath@cs.jhu.edu
ahmad@icsib6.Berkeley.EDU (Subutai Ahmad) (10/12/89)
In article <1989Oct12.050402.9790@boingo.med.jhu.edu>, dave@boingo.med.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? What transfer functions does he allow? Although it is true that any boolean function can be realized with 3 layers, it was shown [1] that you need _at least_ O(2^n/n^2) linear threshold units to implement an arbritrary boolean function. (Note that this result is for n-input to 1 output functions but this is at least as difficult as the n-input to n-output case.) It is quite feasible that with higher order units you can bring this down by a polynomial amount but I doubt that you can make much of a difference to the exponential. Subutai Ahmad International Computer Science Institute ahmad@icsi.berkeley.edu [1] Volper, D.J. and Hampson, S.E. Connectionist Models of Boolean Category Representation. Biological Cybernetics, #54, pp 393-406, 1986.
honavar@goat.cs.wisc.edu (A Buggy AI Program) (10/13/89)
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. > I don't know anything about the proof. However, I have made runs with backprop on a net with 2 input units, 3 hidden units, and 16 output units (all possible boolean functions of 2 variables) and have gotten it to learn successfully to meet the preset criterion. I used real valued activations between 0 and 1, sigmoid output function, and real valued weights. Vasant Honavar honavar@cs.wisc.edu
veenu@cbnewsj.ATT.COM (veenu.r.rashid) (10/13/89)
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. > Yes, this is true as a consequence of simple combinatorics. Does anyone know the number of intermediate nodes (hidden layer) necessary to realize a real valued function [0..1] of n inputs to m outputs. Is there a functional description of such a net anywhere? Inquiring minds would like to know... > >-------------------------------- >Dave Heath heath@cs.jhu.edu Navruze Rashid ruze@mtfmi.att.com -or- veenu@cbnewsj.att.com
demers@beowulf.ucsd.edu (David E Demers) (10/16/89)
>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