betaFeedback

WorksMathematics

DL101 The Representation Capability of Neural Network Models

Abstract

Universal approximation theorems (Cybenko, Funahashi, Hornik & Leshno) provide the mathematical justification for why neural networks are powerful enough to model complex, nonlinear phenomena. Shallow networks can approximate any continuous function on compact sets. Leshno's theorem clarified that non-polynomial activations are necessary for universality, which explains why ReLU, logistic, hyperbolic tangent, and other common activations work (but pure polynomials do not). However, approximation theorems provide no efficiency, training, nor generalization guarantees. They do not indicate how many neurons are needed for a given accuracy, whether gradient descent will find the right parameters, or whether networks trained on finite data will generalize well. Barron provided quantitative error bounds for particular function classes (approximation rates for functions with bounded Fourier norm), whereas Montúfar was the first to show that expressivity grows exponentially with depth (in terms of the number of linear regions). Deep networks are strictly more expressive than shallow ones with the same number of parameters. Depth is fundamentally more powerful than width, providing a rigorous mathematical explanation for the use of deep learning models.

All models are wrong, but some are useful.

George E.P. Box

Deep learning models [1, 6, 7, 8, 15] have a layered structure. A feedforward deep neural network with LL layers can be defined as a function

f:Rn0→RnLf : \mathbb{R}^{n_0} \to\mathbb{R}^{n_L}

constructed by composing affine transformations and nonlinear activations:

f(x)=f(L)∘f(L−1)∘⋯∘f(1)(x),f(x) = f^{(L)} \circ f^{(L-1)} \circ\cdots\circ f^{(1)}(x),

For each layer l=1,…,Ll = 1, \ldots, L,

f(l)(x)=σ(l)(W(l)x+b(l)).f^{(l)}(x) = \sigma^{(l)}\left(W^{(l)}x + b^{(l)}\right).

where x∈Rn0x \in\mathbb{R}^{n_0} is an input vector, nln_l is the number of units (width) in layer ll, W(l)∈Rnl×nl−1W^{(l)} \in\mathbb{R}^{n_l \times n_{l-1}} is the weight matrix of layer ll, b(l)∈Rnlb^{(l)} \in\mathbb{R}^{n_l} is the bias vector of layer ll, and σ(l):R→R\sigma^{(l)} : \mathbb{R} \to\mathbb{R} is the activation function of layer ll, which is applied element-wise.

The depth of the network is LL, and the parameters of the deep learning model are the collection of all weights and biases:

θ={W(l),b(l)}l=1L.\theta= \left\{W^{(l)}, b^{(l)}\right\}_{l=1}^{L}.

Training a deep learning model consists of finding θ\theta that minimizes a loss function L(f(x),y)\mathcal{L}(f(x), y) over a dataset {(xi,yi)}\{(x_i, y_i)\}.

Formally, a deep learning model is just a composition of affine maps and nonlinearities parameterized by weights and biases, which are optimized via loss minimization. As we will see, multilayered neural networks are universal approximators [10, 12, 20, 28, 30].

Universal Approximators

Let us consider the problem of representing general functions of an nn-dimensional real variable, x∈Rnx \in\mathbb{R}^n, by finite linear combinations:

f:Rn→Rf : \mathbb{R}^n \to\mathbb{R}
f(x)=∑j=1hαjσ(∑i=1nwijxi+bj)f(x) = \sum_{j=1}^{h} \alpha_j \sigma\left(\sum_{i=1}^{n} w_{ij}x_i + b_j\right)

which corresponds to a feed-forward neural network with nn inputs, hh hidden neurons, and a single output y=f(x)y = f(x). W=[wij]W = [w_{ij}] is the n×hn \times h weight matrix for the hidden layer, (bj)(b_j) is the h×1h \times1 vector of biases for the hidden neurons, and (αj)(\alpha_j) is the h×1h \times1 weight vector of the output neuron. Finally, σ\sigma is the univariate activation function of the hidden units.

Cybenko's Universal Approximation Theorem

If σ(z)\sigma(z) is a sigmoidal function, i.e. lim⁡z→+∞σ(z)=1\lim_{z\to+\infty}\sigma(z) = 1 and lim⁡z→−∞σ(z)=0\lim_{z\to-\infty}\sigma(z) = 0 (as in the logistic function), George Cybenko [10] proved that functions defined as f(x)f(x) are dense in the space of continuous functions on the unit cube if σ\sigma is any continuous sigmoidal function, such as the logistic function. Cybenko, then at the University of Illinois at Urbana-Champaign, proved the universal approximation theorem for artificial neural networks with sigmoid activation functions:

Neural network representation capability: from universal approximation to the power of depth

Figure 1. Main results discussed in this technical report, according to Google Nano Banana.

Theorem I.1: Universal approximation theorem for artificial neural networks with sigmoid activation functions Let σ\sigma be any continuous discriminatory function. The finite sums of the form

G(x)=∑j=1hαjσ(∑i=1nwijxi+bj)G(x) = \sum_{j=1}^{h} \alpha_j \sigma\left(\sum_{i=1}^{n} w_{ij}x_i+b_j\right)

are dense in C(In)C(I_n). In other words, given any f∈C(In)f \in C(I_n) and ϵ>0\epsilon> 0, there is a sum, G(x)G(x), of the above form, for which

∣G(x)−f(x)∣<ϵ∀x∈In|G(x)-f(x)| < \epsilon\quad\forall x \in I_n

InI_n is the n-dimensional unit hypercube, whereas C(In)C(I_n) is the space of continuous functions in InI_n. The theorem above states that finite superpositions of a fixed, univariate function that is discriminatory can uniformly approximate any continuous function of nn real variables with support in the unit hypercube.

Given that sigmoid activation functions are continuous and discriminatory (lemma B.1), any continuous function can be uniformly approximated by a continuous neural network having only one hidden sigmoid layer with an arbitrary continuous sigmoidal nonlinearity. Therefore, a feed-forward neural network with a single hidden sigmoid layer, acting as a universal approximator, can represent any continuous function, provided that we have enough hidden units.

Funahashi's Universal Approximation Theorem

Independently from Cybenko, Ken-ichi Funahashi [12] also proved that any continuous mapping can be approximately realized multilayer neural networks with at least one hidden layer with sigmoid activation functions.

Theorem I.2: Universal approximation theorem for artificial neural networks with bounded, monotonically increasing activation functions Let ϕ(x)\phi(x) be a non-constant, bounded, and monotonically increasing continuous function. Let KK be a compact subset (bounded closed subset) of Rn\mathbb{R}^{n} and ff a real valued continuous function on KK. Then, for an arbitrary ϵ>0\epsilon> 0, there exists an integer NN and real constants αi\alpha_i, bib_i, and wijw_{ij} such that

f~(x)=∑j=1hαjϕ(∑i=1nwijxi+bj)\widetilde{f}(x) = \sum_{j=1}^{h} \alpha_j \phi\left(\sum_{i=1}^{n} w_{ij}x_i+b_j\right)

satisfies max⁡k∈K∣f(x)−f~(x)∣<ϵ\max_{k \in K}|f(x)-\widetilde{f}(x)| < \epsilon

The above theorem proves that, for an arbitrary ϵ>0\epsilon> 0, there exists a three-layer network, with a ϕ(x)\phi(x) activation function in the hidden layer and a linear output layer, whose output function f~(x)\widetilde{f}(x) approximates f(x)f(x) as close as needed. Obviously, the sigmoid function σ(z)=1/(1−e−z)\sigma(z)=1/(1-e^{-z}) typically used in neural networks satisfies the requirements of ϕ(x)\phi(x), i.e. non-constant, bounded, and monotonically increasing.

Remark. Funahashi’s theorem uses bounded functions. Rectified linear units, ReLU(z)=max⁡{0,z}ReLU(z)=\max\{0,z\}, are not bounded. However, the linear combination ϕ(z)=\phi(z)= ReLU(z−1)−ReLU(z)ReLU(z-1)-ReLU(z) falls within the scope of Funahashi’s theorem, so its conclusion is also valid for ϕ(z)=ReLU(z)\phi(z)=ReLU(z).

Activation functionRangeDerivative
Linear (identity)f(z)=zf(z)=z(−∞,∞)(-\infty,\infty)f′(z)=1f'(z)=1
Logistic (standard sigmoid)f(z)=σ(z)=11+e−zf(z)=\sigma(z)=\frac{1}{1+e^{-z}}(0,1)(0,1)f′(z)=f(z)(1−f(z))f'(z)=f(z)(1-f(z))
Hyperbolic tangent (tanh)f(z)=tanh⁡(z)=ez−e−zez+e−zf(z)=\tanh(z)=\frac{e^z-e^{-z}}{e^z+e^{-z}}(−1,1)(-1,1)f′(z)=1−f2(z)f'(z)=1-f^2(z)
Softmaxfi(z⃗)=ezi∑j=1Kezjf_i(\vec{z})=\frac{e^{z_i}}{\sum_{j=1}^{K}e^{z_j}}[0,1][0,1]∂yi∂xj=∂fi(z⃗)∂xj=yi(δij−yj)\frac{\partial y_i}{\partial x_j}=\frac{\partial f_i(\vec{z})}{\partial x_j}=y_i(\delta_{ij}-y_j)
Softplusf(z)=ln⁡(1+ez)f(z)=\ln(1+e^z)[0,∞)[0,\infty)f′(z)=ex1+ez=11+e−z=σ(z)f'(z)=\frac{e^x}{1+e^z}=\frac{1}{1+e^{-z}}=\sigma(z)
ReLUf(z)=max⁡{0,z}f(z)=\max\{0,z\}[0,∞)[0,\infty)f′(z)=H(z)={1if z>00if z≤0f'(z)=H(z)=\begin{cases}1 & \text{if }z>0\\0 & \text{if }z\leq0\end{cases}
Leaky ReLUf(z)={zif z>0αzif z≤0f(z)=\begin{cases}z & \text{if }z>0\\\alpha z & \text{if }z\leq0\end{cases}(−∞,∞)(-\infty,\infty)f′(z)={1if z>0−αif z≤0f'(z)=\begin{cases}1 & \text{if }z>0\\-\alpha& \text{if }z\leq0\end{cases}

Table 1. Common activation functions in neural networks.

While Cybenko’s and Funahashi’s techniques differs, both support the same conclusion for sigmoidal activations. Funahashi’s proof guarantees the existence of parameters approximating arbitrary spectra, paralleling Cybenko’s measure-separation proof. Both are non-constructive in the sense of parameter selection.

Alternative Activation Functions

Apart from sigmoid functions, such as the logistic function, and the hyperbolic tangent, other activation functions are common in neural networks (see Table I). Cybenko and Funahashi proved the universal approximation capabilities of multi-layered neural networks when using sigmoid activation functions in the hidden layer. What happens with other activation functions?

Hornik's Approximation Theorems

The Hornik theorems [19, 20] formalize the universal approximation capabilities of multilayer feedforward neural networks for bounded and continuous activation functions:

References

  1. [1]Aggarwal, C. C. Neural Networks and Deep Learning: A Textbook, 2nd edition. Springer, 2023.
  2. [2]Arnold, V. On the representation of continuous functions of three variables as superpositions of continuous functions of two variables [in Russian]. Doklady Akademii Nauk SSSR 114, 4 (1957), 679–681. English translation in American Mathematical Society Translations, Series 2, Vol. 28, pp. 51–54, 1963.DOI
  3. [3]Banach, S. Sur les fonctionnelles linéaires [On Linear Functionals, in French]. Studia Mathematica 1 (1929), 211–216, 223–239.DOI
  4. [4]Banach, S. Théorie des opérations linéaires [Theory of Linear Operations, in French], vol. 1 of Monografie Matematyczne [Mathematical Monographs]. M-W, Warsaw, 1932. Chapter IV of this monograph provides the definitive, comprehensive presentation of the Hahn–Banach extension theorem alongside its immediate geometric and analytic consequences.
  5. [5]Barron, A. R. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory 39, 3 (1993), 930–945.DOI
  6. [6]Berzal, F. Redes Neuronales & Deep Learning - Volumen I: Entrenamiento de redes neuronales artificiales [Neural Networks and Deep Learning - Volume I: Training Artificial Neural Networks, in Spanish]. Amazon KDP, Granada, Spain, 2019.
  7. [7]Berzal, F. Redes Neuronales & Deep Learning - Volumen II: Regularización, optimización & arquitecturas especializadas [Neural Networks and Deep Learning - Volume II: Regularization, Optimization, and Specialized Architectures, in Spanish]. Amazon KDP, Granada, Spain, 2019.
  8. [8]Bishop, C. M., and Bishop, H. Deep Learning: Foundations and Concepts. Springer, 2024.
  9. [9]Borel, E. Sur quelques points de la théorie des fonctions [On some points of the theory of functions, in French]. Annales scientifiques de l’École Normale Supérieure [Scientific Annals of the École Normale Supérieure] 12 (1895), 9–55.
  10. [10]Cybenko, G. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems 2, 4 (1989), 303–314.
  11. [11]Cybenko, G. Correction: Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems 5 (1992), 455.
  12. [12]Funahashi, K.-I. On the approximate realization of continuous mappings by neural networks. Neural Networks 2, 3 (1989), 183–192.DOI
  13. [13]Gallant, A. R., and White, H. L. There exists a neural network that does not make avoidable mistakes. In Proceedings of the IEEE International Conference on Neural Networks (ICNN ’88) (San Diego, CA, USA, July 1988), vol. 1, pp. 657–664.
  14. [14]Gallant, A. R., and White, H. L. On learning the derivatives of an unknown mapping with multilayer feedforward networks. Neural Networks 5, 1 (1992), 129–138.DOI
  15. [15]Goodfellow, I., Bengio, Y., and Courville, A. Deep Learning. MIT Press, 2016.
  16. [16]Hahn, H. Über lineare Gleichungssysteme in linearen Räumen [On Linear Systems of Equations in Linear Spaces, in German]. Journal für die reine und angewandte Mathematik [Journal for Pure and Applied Mathematics], a.k.a. Crelle’s Journal 157 (1927), 214–229. Crelle’s Journal in honor to its founder, August Leopold Crelle.
  17. [17]Hecht-Nielsen, R. Kolmogorov’s Mapping Neural Network Existence Theorem. In Proceedings of the IEEE International Conference on Neural Networks (ICNN ’87) (San Diego, CA, 1987), vol. III, IEEE, pp. 11–13.
  18. [18]Heine, E. Die Elemente der Functionenlehre [The Elements of the Theory of Functions, in German]. Journal für die reine und angewandte Mathematik [Journal for Pure and Applied Mathematics], a.k.a. Crelle’s Journal 74 (1872), 172–188.DOI
  19. [19]Hornik, K. Approximation capabilities of multilayer feedforward networks. Neural Networks 4, 2 (1991), 251–257.DOI
  20. [20]Hornik, K., Stinchcombe, M., and White, H. Multilayer feedforward networks are universal approximators. Neural Networks 2, 5 (1989), 359–366.DOI
  21. [21]Hornik, K., Stinchcombe, M., and White, H. Universal approximation of an unknown mapping and its derivatives using multilayer feedforward networks. Neural Networks 3, 5 (1990), 551–560.DOI
  22. [22]Irie, B., and Miyake, S. Capabilities of three-layered perceptrons. In Proceedings of the IEEE International Conference on Neural Networks (ICNN ’88) (San Diego, CA, USA, July 1988), vol. 1, pp. 641–648.
  23. [24]Kakutani, S. Concrete representation of abstract (M)-spaces. (A characterization of the space of continuous functions). Annals of Mathematics. Second Series 42, 4 (1941), 994–1024.DOI
  24. [25]Kolmogorov, A. N. On the representation of continuous functions of many variables by superposition of continuous functions of one variable and addition [in Russian]. Doklady Akademii Nauk SSSR 114, 5 (1957), 953–956. English translation in American Mathematical Society Translations, Series 2, Vol. 28, pp. 55–59, 1963.
  25. [26]Lapedes, A., and Farber, R. How neural nets work. In Proceedings of the 1st International Conference on Neural Information Processing Systems (Cambridge, MA, USA, 1987), NIPS’87, MIT Press, pp. 442–456.
  26. [27]Lebesgue, H. Leçons sur l’intégration et la recherche des fonctions primitives [Lectures on Integration and the Search for Antiderivatives, in French]. Gauthier-Villars, Paris, 1904.
  27. [28]Leshno, M., Lin, V. Y., Pinkus, A., and Schocken, S. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Networks 6, 6 (1993), 861–867.DOI
  28. [29]Markov, A. A. On mean values and exterior densities. Matematicheskii Sbornik [Mathematical Compilation], Moscow Mathematical Society 4, 1 (1938), 165–191.
  29. [30]Montúfar, G., Pascanu, R., Cho, K., and Bengio, Y. On the number of linear regions of deep neural networks. In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2 (Cambridge, MA, USA, 2014), NIPS’14, MIT Press, pp. 2924–2932.arxiv.org/abs/1402.1869
  30. [31]Montúfar, G., Pascanu, R., Cho, K., and Bengio, Y. On the number of linear regions of deep neural networks, 2014. arXiv:1402.1869.arxiv.org/abs/1402.1869
  31. [32]Paley, R. E. A. C., and Wiener, N. Fourier Transforms in the Complex Domain, vol. 19 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 1934.
  32. [34]Raghu, M., Poole, B., Kleinberg, J., Ganguli, S., and Sohl-Dickstein, J. On the expressive power of deep neural networks. In International Conference on Machine Learning (2017), PMLR, pp. 2847–2854.arxiv.org/abs/1606.05336
  33. [35]Riesz, F. Sur les opérations fonctionnelles linéaires [On linear functional operations, in French]. Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences [Weekly Reports of the Academy of Sciences], Paris 149 (1909), 974–977.
  34. [36]Serra, T., Tjandraatmadja, C., and Ramalingam, S. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning (2018), PMLR, pp. 4558–4566.arxiv.org/abs/1711.02114
  35. [37]Sprecher, D. A. On the structure of continuous functions of several variables. Transactions of the American Mathematical Society 115 (1965), 340–355.DOI
  36. [38]Telgarsky, M. Benefits of depth in neural networks. In Conference on Learning Theory (2016), PMLR, pp. 1517–1539.arxiv.org/abs/1602.04485

Paper details

vlnc:W_z9dcu8kf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents