It has been proven by Cybenko in 1989 that neural networks are universal function approximators, but I have a related question that is somewhat different.

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 # of weights = $L \cdot n^2$.

My question is: If the # of weights is not allowed to grow exponentially as $n$, can a deep neural network realize 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 # of weights are polynomially bounded.

[ Recently I have a little 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.

up vote 2 down vote accepted

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.

  • 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. – Yan King Yin Aug 9 at 7:00
  • @YanKingYin, The D^D is issue #1. For each output bit there are 2^D cells in the truth table (permutations of input mapped to output) for an arbitrary Boolean expression, so that's the number of bits required to represent the arbitrary function. There are D output bits per your system requirement, so we have D truth tables requiring an absolute minimum of 2^D bits of learning for each. D times 2^D does not equal D^D. For large D values, it is much less. Issue #2 is that you didn't factor in the number of bits in the digital representations of the parameters in the L-1 attenuation matrices. – Douglas Daseeco Aug 15 at 13:19
  • @YanKingYin, did I explain clearly enough in the previous comment? – Douglas Daseeco Aug 15 at 13:19
  • 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. – Yan King Yin 2 days ago
  • 1
    @YanKingYin, Yes, and thank you, but it is not my cleverness. Ergodic theory began with the desire to find the mathematical link between known good classical thermodynamics and quantum theory arising from the Bohr model of the atom through the birth of statistical physics. Those theorists with whom Claude Shannon hob-nobbed led to Shannon's information theory. The definition of a bit as a base 2 logarithm and its practical use in simplifying information calculations was Shannon's cleverness and is sprinkled throughout the AI literature today for just such problems as the one in your Q.. – Douglas Daseeco 2 days ago

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.

  • 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. – Yan King Yin Aug 12 at 8:50
  • What you open with, Manuel, is true about DEMONSTRATION, but not about PROOF. The computing world sprung from funding that was allocated after proofs were established and agreed upon that automation would improve a number of military defense conditions. On the machine learning plane, much theory went into proving convergence for ANN back propagation and considering direction and magnitude issues in gradient descent before any software actually worked. I do agree that if we can't get real software to do what the theory suggests is viable, then our theory may be flawed. – Douglas Daseeco Aug 12 at 22:02
  • @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. – Manuel Rodriguez Aug 14 at 17:43
  • Software that shows an expected result for a sample input is called a proof of concept, but it is a demonstration. Even after a POC shows promise and the design is found to be successful in field use, it is not accepted as an extension of technology if the principles of scientific validation are absent. Basis for the software must be logically consistent with existing theory; apparatus, a set of experimental cases, and analysis must be carefully assembled; and theory and empirical result must match convincingly and repeatably. For example, back propagation has such a match. – Douglas Daseeco Aug 14 at 22:42
  • @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. – Manuel Rodriguez Aug 15 at 14:33

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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