On the capabilities of multilayer perceptrons

By Eric B. Baum. 1988

Abstract What is the smallest multilayer perceptron able to compute arbitrary and random functions? Previous results show that a net with one hidden layer containing N − 1 threshold units is capable of implementing an arbitrary dichotomy of N points. A construction is presented here for implementing an arbitrary dichotomy with one hidden layer containing [ N d ] units, for any set of N points in general position in d dimensions. This is in fact the smallest such net as dichotomies which cannot be implemented by any net with fewer units are described. Several constructions are presented of one-hidden-layer nets implementing arbitrary functions into the e-dimensional hypercube. One of these has only [ 4N d ][ e [ log 2 ( N d) ]] units in its hidden layer. Arguments based on a function counting theorem of Cover establish that any net implementing arbitrary functions must have at least Ne log 2 (N) weights, so that no net with one hidden layer containing less than Ne/(d log2(N)) units will suffice. Simple counts also show that if the weights are only allowed to assume one of ng possible values, no net with fewer than Ne log 2 (n g ) weights will suffice. Thus the gain coming from using real valued synapses appears to be only logarithmic. The circuit implementing functions into the e hypercube realizes such logarithmic gains. Since the counting arguments limit below only the number of weights, the possibility is suggested that, if suitable restrictions are imposed on the input vector set to avoid topological obstructions, two-hidden-layer nets with O(N) weights but only O(√N) threshold units might suffice for arbitrary dichotomies. Interesting and potentially sufficient restrictions include (a) if the vectors are binary, i.e., lie on the d hypercube or (b) if they are randomly and uniformly selected from a bounded region.

Subfields: Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Model Architectures

Citations in the corpus

The jamming transition as a paradigm to understand the loss landscape of deep neural networks (2018, background): “[17] Eric B Baum, “On the capabilities of multilayer percep-”
No bad local minima: Data independent training error guarantees for multilayer neural networks (2016, background): “…we state the following important result, which a special case of [1, lemma 13], Note that this result is tight, in the sense that the minimal hidden layer width d 1 = ⌈ N/d 0 ⌉ , is exactly the same minimal width which ensures a MNN can implement any dichotomy [3] for inputs in general position.”
Exponentially vanishing sub-optimal local minima in multilayer neural networks (2017, methodology): “This construction is a variant of (Baum, 1988, Theorem 1), except we use LReLU without bias and MSE – instead of threshold units with bias and MCE.”
No Training Required: Exploring Random Encoders for Sentence Classification (2019, background): “The idea of using random weights is almost as old as neural networks, ultimately going back to ideas in multi-layer perceptrons with fixed randomly initialized first layers (Gamba et al., 1961; Borsellino & Gamba, 1961; Baum, 1988), or what Minsky and Papert call Gamba perceptrons (Minsky & Papert, ”
Universal Approximation using Incremental Constructive Feedforward Networks with Random Hidden Nodes (2006, background): “Baum [11] has claimed that (seen from simulations for SLFN with additive hidden nodes) one may ﬁx the weights of the connections on one level and simply adjust the connections on the other level and no gain is possible by using an algorithm able to adjust the weights on both levels simultaneously.”
Learning capability and storage capacity of two-hidden-layer feedforward networks (2003, background): “It is interesting to note that our proposed network not only has the features expected by Baum [18] and Bartlett [19], but also shows Baum's claim valid for sigmoid networks .”
What are Extreme Learning Machines? Filling the Gap Between Frank Rosenblatt’s Dream and John von Neumann’s Puzzle (2015, background): “In addition, in contrast to the misunderstanding that those earlier works were not referred, we have even referred to Baum (1988) [31]’s work and White’s QuickNet (1989) [54] in our 2008 works [4], [5], which we consider much earlier than Schmidt, et al. (1992) [1] and RVFL (1994) [2] in the…”
Extreme learning machine: RBF network case (2004, background): “…that ˜ =1 o j − t j = 0, i.e., there exist β i , µ i and σ i such that The above N equations can be written compactly as: where Similar to SLFNs [9], [4], H is called the hidden layer output matrix of the RBF network; the i th column of H is the output of the i th kernel with respect to inputs”
Approximation theory of the MLP model in neural networks (1999, methodology): “The problem of being able to arbitrarily separate N generic points in Rn into two sets by use of a one hidden layer perceptron model with Heaviside activation function (and one output) was considered by Baum (1988). He showed that the problem is solvable if one uses at least [N=n] units in the hidde”