Estimates of Storage Capacity of Multilayer Perceptron with Threshold Logic Hidden Units.

We estimate the storage capacity of multilayer perceptron with n inputs, h(1) threshold logic units in the first hidden layer and 1 output. We show that if the network can memorize 50% of all dichotomies of a randomly selected N-tuple of points of R(n) with probability 1, then N</=2(nh(1)+1), while at 100% memorization N</=nh(1)+1. Furthermore, if the bounds are reached, then the first hidden layer must be fully connected to the input. It is shown that such a network has memory capacity (in the sense of Cover) between nh(1)+1 and 2(nh(1)+1) input patterns and for the most efficient networks in this class between 1 and 2 input patterns per connection. Comparing these results with the recent estimates of VC-dimension we find that in contrast to a single neuron case, the VC-dimension exceeds the capacity for a sufficiently large n and h(1). The results are based on the derivation of an explicit expression for the number of dichotomies which can be implemented by such a network for a special class of N-tuples of input patterns which has a positive probability of being randomly chosen.