Answers.Body: <p><strong>What is Proven</strong></p>
  <p>The question references the proof of <a href="https://pdfs.semanticscholar.org/05ce/b32839c26c8d2cb38d5529cf7720a68c3fab.pdf" rel="nofollow noreferrer">Approximation by Superpositions of a Sigmoidal Function, G. Cybenko, 1989, Mathematics of Control, Signals, and Systems</a>.</p>
  <p>The 1989 proof stated that the network, made of activations that were required to be, &quot;Of continuous sigmoidal non-linearity,&quot; could, &quot;Uniformly approximate any continuous function of n real variables,&quot; 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.</p>
  <p>The question defines the system as an arbitrary mapping from input bit vector</p>
  <blockquote>
  <p><span class="math-container">$I: { i_1, \; \dots, \; i_n}$</span></p>
  </blockquote>
  <p>to output bit vector</p>
  <blockquote>
  <p><span class="math-container">$O: { o_1, \; \dots, \; o_n}$</span></p>
  </blockquote>
  <p>It was further back proven that such a mapping can be accomplished with one Boolean expressions for each output bit.  For all <span class="math-container">$2^n$</span> 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.</p>
  <p>There are techniques for reducing redundancy in the array of Boolean expressions, which is critical to VLSI chip layout.</p>
  <p>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.</p>
  <p><strong>Estimating Layer Depth Requirements</strong></p>
  <p>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?</p>
  <p>The question proposes that there are <span class="math-container">$2^n$</span> to the power of <span class="math-container">$2^n$</span> permutations.  The mapping of each input bit vector to the desired output bit state can be represented by a truth table of <span class="math-container">$n$</span> binary dimensions.</p>
  <p>Each output is an independent bit, meaning the <span class="math-container">$2^n$</span>-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 <span class="math-container">$2n$</span> freedoms of motion for the mapping of I to O.</p>
  <p>For the case where the input is a bit vector of <span class="math-container">$n$</span> bits, where <span class="math-container">$n$</span> is the number of activations for any one of <span class="math-container">$L$</span> layers, the total number of activations in the network <span class="math-container">$a_t$</span> and the total number of scalar elements for all attenuation matrices (the parameters that represent training state) <span class="math-container">$q_t$</span> for the network is as follows.</p>
  <blockquote>
  <p><span class="math-container">$a_t = \sum_{\, 0 = v}^{L - 1} \; n_v$</span></p>
  <blockquote>
  <blockquote>
  <p><span class="math-container">$= n \, L$</span></p>
  </blockquote>
  </blockquote>
  <p><span class="math-container">$p_t = \sum_{\, 0 = v}^{L - 2} \; n_v^2$</span></p>
  <blockquote>
  <blockquote>
  <p><span class="math-container">$= n^2 \, (L-1)$</span></p>
  </blockquote>
  </blockquote>
  </blockquote>
  <p>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.</p>
  <blockquote>
  <p><span class="math-container">$b_t = 64 \, (L - 1) \, n^2$</span></p>
  </blockquote>
  <p>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.</p>
  <p>Thus we have a formulation of the information theory comparison inferred by the question, and can reduce it.</p>
  <blockquote>
  <p><span class="math-container">$2^{2n} \le 64 \, (L - 1) \, n^2$</span></p>
  <p><span class="math-container">$L \ge 1 + \frac {2^{2n-6}} {n^2}$</span></p>
  </blockquote>
  <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-09T07:00:13.333Z
Answers.Text: 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.
Answers.UserDisplayName: Yan King Yin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T11:31:55.417Z
Answers.Text: 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.
Answers.UserDisplayName: Yan King Yin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T11:38:23.780Z
Answers.Text: PS:  the link to that answer is:
  https://math.stackexchange.com/questions/1895498/possible-boolean-functions-in-n-dimensional-space
Answers.UserDisplayName: Yan King Yin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T11:53:07.133Z
Answers.Text: Yes, but you're just asking the same question as that question, and the well-established answer is 2^(2^n)  :)
Answers.UserDisplayName: Yan King Yin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T11:57:48.310Z
Answers.Text: 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.
Answers.UserDisplayName: Yan King Yin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-16T17:01:54.633Z
Answers.Text: OK, I can understand your derivation now, it assumes finite-precision floating-point and you use an argument based on counting the number of bits of information.  Which is clever, but what if I assume infinite precision?  My argument based on "degree theory" also suggests the # layers would grow exponentially.  Which, at least, agrees with your conclusion :)
Answers.UserDisplayName: Yan King Yin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-06T04:31:33.483Z
Answers.LastActivityDate: 2018-08-16T13:07:26.070Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: Douglas Daseeco
Body: <p>It has been proven in the paper "<a href="https://pdfs.semanticscholar.org/05ce/b32839c26c8d2cb38d5529cf7720a68c3fab.pdf" rel="nofollow noreferrer">Approximation by Superpositions of a Sigmoidal Function</a>" (by Cybenko, in 1989) that neural networks are universal function approximators.  I have a related question. </p>
  
  <p>Assume the neural network's input and output vectors are of the same dimension <span class="math-container">$n$</span>. Consider the set of <strong>binary-valued</strong> functions from <span class="math-container">$\{ 0,1 \}^n$</span> to <span class="math-container">$\{ 0,1 \}^n$</span>.  There are <span class="math-container">$(2^n)^{(2^n)}$</span> such functions. The number of parameters in a (deep) neural network is <strong>much smaller</strong> than the above number.  Assume the network has <span class="math-container">$L$</span> layers, each layer is <span class="math-container">$n \times n$</span> fully-connected, then the total number of weights is <span class="math-container">$L \cdot n^2$</span>.</p>
  
  <p>If the number of weights is <strong>not</strong> allowed to grow exponentially as <span class="math-container">$n$</span>, can a deep neural network approximate <strong>all</strong> the binary-valued functions of size <span class="math-container">$n$</span>?</p>
  
  <p>Cybenko's proof seems to be based on the <strong>denseness</strong> 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.</p>
  
  <p>I have a theory. If we replace the activation function of an ANN with a polynomial, say cubic one，then after <span class="math-container">$L$</span> layers, the composite polynomial function would have degree <span class="math-container">$3^L$</span>.  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.</p>
  
  <p>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 <em>doubly</em> 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.</p>
  
Tags: <neural-networks><machine-learning><proofs>
Title: How can a neural network approximate all functions when the weights are not allowed to grow exponentially?
UserDisplayName: Yan King Yin
ThreadText: # How can a neural network approximate all functions when the weights are not allowed to grow exponentially?
  
  (Asked by: username_0 on 2018-08-05)
  
  It has been proven in the paper "[Approximation by Superpositions of a Sigmoidal Function](https://pdfs.semanticscholar.org/05ce/b32839c26c8d2cb38d5529cf7720a68c3fab.pdf)" (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.
  
  **Tags:** neural-networks, machine-learning, proofs
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-08-06. Score: 4 | Accepted answer
  
  **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](https://pdfs.semanticscholar.org/05ce/b32839c26c8d2cb38d5529cf7720a68c3fab.pdf).
  
  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.
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_0**: 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.  
  > **username_0**: PS:  the link to that answer is: https://math.stackexchange.com/questions/1895498/possible-boolean-functions-in-n-dimensional-space  
  > **username_0**: Yes, but you're just asking the same question as that question, and the well-established answer is 2^(2^n)  :)  
  > **username_0**: 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.  
  > **username_0**: OK, I can understand your derivation now, it assumes finite-precision floating-point and you use an argument based on counting the number of bits of information.  Which is clever, but what if I assume infinite precision?  My argument based on "degree theory" also suggests the # layers would grow exponentially.  Which, at least, agrees with your conclusion :)  
  
  ---
  
  