It has been proven in the paper "Approximation by Superpositions of a Sigmoidal Function" (by Cybenko, in 1989) that neural networks are universal function approximators. I have a related question.

Assume the neural network's input and output vectors are of the same dimension $n$. Consider the set of binary-valued functions from $\{ 0,1 \}^n$ to $\{ 0,1 \}^n$. There are $(2^n)^{(2^n)}$ such functions. The number of parameters in a (deep) neural network is much smaller than the above number. Assume the network has $L$ layers, each layer is $n \times n$ fully-connected, then the total number of weights is $L \cdot n^2$.

If the number of weights is not allowed to grow exponentially as $n$, can a deep neural network approximate all the binary-valued functions of size $n$?

Cybenko's proof seems to be based on the denseness of the function space of neural network functions. But this denseness does not seem to guarantee that a neural network function exists when the number of weights are polynomially bounded.

I have a theory. If we replace the activation function of an ANN with a polynomial, say cubic one,then after $L$ layers, the composite polynomial function would have degree $3^L$. In other words, the degree of the total network grows exponentially. In other words, its "complexity" measured by the number of zero-crossings, grows exponentially. This seems to remain true if the activation function is sigmoid, but it involves the calculation of the "topological degree" (a.k.a. mapping degree theory), which I have not the time to do yet.

According to my above theory, the VC dimension (roughly analogous to the zero-crossings) grows exponentially as we add layers to the ANN, but it cannot catch up with the doubly exponential growth of Boolean functions. So the ANN can only represent a fraction of all possible Boolean functions, and this fraction even diminishes exponentially. That's my current conjecture.


What is Proven

The question references the proof of Approximation by Superpositions of a Sigmoidal Function, G. Cybenko, 1989, Mathematics of Control, Signals, and Systems.

The 1989 proof stated that the network, made of activations that were required to be, "Of continuous sigmoidal non-linearity," could, "Uniformly approximate any continuous function of n real variables," so, as the question stated, the proof doesn't directly apply to 1-bit discrete outputs. Note that the network is expected to merely approximate the desired circuit behavior.

The question defines the system as an arbitrary mapping from input bit vector

$I: { i_1, \; \dots, \; i_n}$

to output bit vector

$O: { o_1, \; \dots, \; o_n}$

It was further back proven that such a mapping can be accomplished with one Boolean expressions for each output bit. For all $2^n$ possible input vector permutations, there exists a Boolean expression made up of AND and NOT operations that calculates a result that matches any arbitrary logical truth table.

There are techniques for reducing redundancy in the array of Boolean expressions, which is critical to VLSI chip layout.

Without the retention of state anywhere in the network other than the attenuation matrix (parameters), the system is not Turing complete. However, with regard to the ability to realize Boolean expressions in describing the mapping, given an arbitrary number of layers, the network is complete.

Estimating Layer Depth Requirements

Only one inner layer is required in the 1989 proof, so how many layers would it take for an accurate n-bit-to-n-bit mapping to be learned?

The question proposes that there are $2^n$ to the power of $2^n$ permutations. The mapping of each input bit vector to the desired output bit state can be represented by a truth table of $n$ binary dimensions.

Each output is an independent bit, meaning the $2^n$-bit representations of unique Boolean functions that could produce each output bit is not tied to any other output channel. As would be expected, there are $2n$ freedoms of motion for the mapping of I to O.

For the case where the input is a bit vector of $n$ bits, where $n$ is the number of activations for any one of $L$ layers, the total number of activations in the network $a_t$ and the total number of scalar elements for all attenuation matrices (the parameters that represent training state) $q_t$ for the network is as follows.

$a_t = \sum_{\, 0 = v}^{L - 1} \; n_v$

$= n \, L$

$p_t = \sum_{\, 0 = v}^{L - 2} \; n_v^2$

$= n^2 \, (L-1)$

If IEEE 64 bit floating point numbers are used for each element in the attenuation matrix, we can calculate the number of bits available in the training parametrization.

$b_t = 64 \, (L - 1) \, n^2$

It would be normal today to use ReLU, leaky ReLU, or some other more quickly convergent activation instead of sigmoid for all layers but the last and use a simple binary threshold for the last.

Thus we have a formulation of the information theory comparison inferred by the question, and can reduce it.

$2^{2n} \le 64 \, (L - 1) \, n^2$

$L \ge 1 + \frac {2^{2n-6}} {n^2}$

This is a rough threshold. For a highly reliable training for the binary inputs to binary outputs, the number of layers should be well above the threshold.

Below the threshold the trainability of the mapping will degrade to an inadequate approximation for most applications because of signal saturation in the back propagation mechanism.

  • $\begingroup$ Thanks for your answer, still trying to digest it. From my naive understanding, a function from D -> D is the same as D^D. For n = 2, my counting is 4^4 = 256 but your counting is 2^4 = 16. There's a huge difference. For each function, we need to define f(0), f(1), f(2), f(3), ie 4 numbers. Each number can be one of {0,1,2,3}. So we have 4^4 = 256 combinations. $\endgroup$ – Yan King Yin Aug 9 '18 at 7:00
  • $\begingroup$ Thanks, but I still think you counted wrong. What you have is the number of Boolean functions on {0,1}^n, which is 2^(2^n). I found this answer on the web. But now we have n such outputs!! That makes the count equal to the above answer^n = [2^(2^n)]^n = 2^(n 2^n) = (2^n)^(2^n) which agrees with my original count. $\endgroup$ – Yan King Yin Aug 16 '18 at 11:31
  • $\begingroup$ PS: the link to that answer is: math.stackexchange.com/questions/1895498/… $\endgroup$ – Yan King Yin Aug 16 '18 at 11:38
  • $\begingroup$ Yes, but you're just asking the same question as that question, and the well-established answer is 2^(2^n) :) $\endgroup$ – Yan King Yin Aug 16 '18 at 11:53
  • $\begingroup$ The catch is here: if you have a truth table, you have to fill out EVERY row of the table to get ONE function. For each row there are 2 ways, ie {0,1}, to fill it. So there are 2^(2^n) different ways to fill those truth tables. $\endgroup$ – Yan King Yin Aug 16 '18 at 11:57

Cybenko hasn't proven anything. His paper is not the answer to a problem but it describes the question. A proof for a neural network problem is the realization in software (for example tensorflow) or in hardware (nvidia gpu).

The OP was about a proof for universal function approximation of neural networks. After recognizing how the proof doesn't look like it is important to give an example how to make it right. In a blogpost about the Tensorflow software I've found a proof. It is based on a Python script and implements a universal function approximator. The author doesn't call his text a proof, instead it is named an “implementation” but it is the same.

Let us make a short example. Suppose I write a formula down, which describes a neural network: output=sum(weight*neuron) for all x over i. Then I add the sigmoid activation function which is g(a) = 1/(1+exp(−a)) and now I call my formulas a proof, because it is mathematical correct description of neural networks. How many people here in the forum would agree, that I have done something important in the domain of neural networks which is equal to prove something? I hope nobody, because I haven't invested any effort. The amount of time needed to write down two simple formulas was under 2 seconds and nobody will profit from it. It was a pseudo proof and in the above cited blogpost the real proof is given.

  • $\begingroup$ Despite the inaccurate math language, you have a point. An actual experiment can provide some example data points. In the case n = 2, there'd be 256 binary functions and you may try to find a single NN configuration that can learn them all. For n = 3 there'd be 16777216 functions, too much to be tested on a real computer. One may exploit symmetries to cut down the cases. $\endgroup$ – Yan King Yin Aug 12 '18 at 8:50
  • $\begingroup$ @DouglasDaseeco A proof in mathematics is usually done with a formal language. A formal language is a programming language, for example LISP, Python or APL. If someone has programmed the sourcecode, he has described the problem in a formal mathematical notation. We can discuss, which language is valid. For example somebody may argue, that only Forth is a formal language, but not Visual-Basic, but a proof without a language is uncommon. $\endgroup$ – Manuel Rodriguez Aug 14 '18 at 17:43
  • $\begingroup$ @DouglasDaseeco Your critics about software is right. Most programs doesn't work, and if they they work they doesn't bring science forward. But, if you criticizing runable source code so much, what are you saying about a formula like “f(x)=sum(a+b)*sin(i) over x”? This formula is below the standards of executable programs, because it can't executed in a virtual machine. $\endgroup$ – Manuel Rodriguez Aug 15 '18 at 14:33
  • $\begingroup$ Waiting to publish until something works is an anti-pattern in Academia. It is equal to publish only positive results and prevents other from learning of failure. What AI needs is a bugtracker which is common in software development, that means, especially if a theory doesn't fit to the measurement it gets published. $\endgroup$ – Manuel Rodriguez Aug 17 '18 at 8:16
  • $\begingroup$ A proof is not an implementation in software, in general. $\endgroup$ – nbro Feb 7 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.