Answers.Body: <p>Multilayer Perceptron (MLP) can theoretically approximate any bounded, continuous function. There's no guarantee for a discontinuous function. There are plenty of important discontinuous functions, like, say, the prime counting function.</p>
  <p>The <a href="https://en.wikipedia.org/wiki/Prime-counting_function" rel="nofollow noreferrer">prime counting function</a> <span class="math-container">$\pi(n)$</span> is simply equal to the number of primes less than or equal to <span class="math-container">$n$</span>. It has a discontinuity about each prime <span class="math-container">$p$</span>, so good luck trying to approximate this with a neural network!</p>
  <p>However, this function is extensively studied and extremely important in number theory. See the <a href="https://en.wikipedia.org/wiki/Riemann_hypothesis" rel="nofollow noreferrer">Riemann hypothesis</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-12-22T17:36:01.180Z
Answers.Text: There are guarantees for discontinuous functions, since universal approximation results also exist for $L^p$-spaces (see for example https://openreview.net/pdf?id=O-XJwyoIF-k). So the reason for being bad at approximating $\pi$ must be something else.
Answers.UserDisplayName: Stefan Perko
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2016-08-04T21:05:44.587Z
Answers.LastActivityDate: 2021-01-22T14:34:52.270Z
Answers.LastEditDate: 2021-01-22T14:34:52.270Z
Answers.UserDisplayName: bpachev
Answers.Body: <p>While I'm not familiar with any explicit statements regarding what a Multilayer Perceptron (MLP) <em>cannot</em> learn, I can provide some further detail on the positive statements you made about MLP capabilities:</p>
  
  <p>A MLP with a single hidden layer is capable of what is commonly termed <a href="https://en.wikipedia.org/wiki/Universal_approximation_theorem" rel="nofollow noreferrer">'Universal Function Approximation'</a>, i.e. it can approximate any bounded continuous function to an arbitrary degree of accuracy. With two hidden layers, the boundness restriction is removed <a href="http://link.springer.com/article/10.1007/BF02551274" rel="nofollow noreferrer">[Cybenko, 1988]</a>.</p>
  
  <p><a href="http://www.sciencedirect.com/science/article/pii/089360809190009T" rel="nofollow noreferrer">This paper</a> goes on to demonstrate that this is true for a wide range of activation functions (not necessarily nonlinear). 3 layer MLPs are also capable of representing any boolean function (although they may require an exponential number of neurons).</p>
  
  <p>See also <a href="https://cstheory.stackexchange.com/questions/7894/universal-function-approximation">this interesting answer</a> on CS SE about other Universal approximators.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-03T21:08:03.797Z
Answers.LastActivityDate: 2016-08-03T21:08:03.797Z
Answers.LastEditDate: 2017-04-13T12:32:34.750Z
Answers.UserDisplayName: NietzscheanAI
Body: <p>In 1969, Seymour Papert and Marvin Minsky showed that Perceptrons could not learn the XOR function.</p>
  <p>This was solved by the backpropagation network with at least one hidden layer. This type of network can learn the XOR function.</p>
  <p>I believe I was once taught that every problem that could be learned by a backpropagation neural network with multiple hidden layers, could also be learned by a backpropagation neural network with a single hidden layer. (Although possibly a nonlinear activation function was required).</p>
  <p>However, it is unclear to me what the limits are to backpropagation neural networks themselves. Which patterns <strong>cannot</strong> be learned by a neural network trained with gradient descent and backpropagation?</p>
  
Tags: <neural-networks><machine-learning><backpropagation><universal-approximation-theorems><computational-learning-theory>
Title: What are the learning limitations of neural networks trained with backpropagation?
UserDisplayName: S.L. Barth is on codidact.com
ThreadText: # What are the learning limitations of neural networks trained with backpropagation?
  
  (Asked by: username_0 on 2016-08-03)
  
  In 1969, Seymour Papert and Marvin Minsky showed that Perceptrons could not learn the XOR function.
  
  This was solved by the backpropagation network with at least one hidden layer. This type of network can learn the XOR function.
  
  I believe I was once taught that every problem that could be learned by a backpropagation neural network with multiple hidden layers, could also be learned by a backpropagation neural network with a single hidden layer. (Although possibly a nonlinear activation function was required).
  
  However, it is unclear to me what the limits are to backpropagation neural networks themselves. Which patterns **cannot** be learned by a neural network trained with gradient descent and backpropagation?
  
  **Tags:** neural-networks, machine-learning, backpropagation, universal-approximation-theorems, computational-learning-theory
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2016-08-04. Score: 3
  
  Multilayer Perceptron (MLP) can theoretically approximate any bounded, continuous function. There's no guarantee for a discontinuous function. There are plenty of important discontinuous functions, like, say, the prime counting function.
  
  The [prime counting function](https://en.wikipedia.org/wiki/Prime-counting_function) $\pi(n)$ is simply equal to the number of primes less than or equal to $n$. It has a discontinuity about each prime $p$, so good luck trying to approximate this with a neural network!
  
  However, this function is extensively studied and extremely important in number theory. See the [Riemann hypothesis](https://en.wikipedia.org/wiki/Riemann_hypothesis).
  
  > **Comments:**
  > **username_2**: There are guarantees for discontinuous functions, since universal approximation results also exist for $L^p$-spaces (see for example https://openreview.net/pdf?id=O-XJwyoIF-k). So the reason for being bad at approximating $\pi$ must be something else.  
  
  ---
  
  ### Answer by username_3 on 2016-08-03. Score: 2
  
  While I'm not familiar with any explicit statements regarding what a Multilayer Perceptron (MLP) *cannot* learn, I can provide some further detail on the positive statements you made about MLP capabilities:
  
  A MLP with a single hidden layer is capable of what is commonly termed ['Universal Function Approximation'](https://en.wikipedia.org/wiki/Universal_approximation_theorem), i.e. it can approximate any bounded continuous function to an arbitrary degree of accuracy. With two hidden layers, the boundness restriction is removed [[Cybenko, 1988]](http://link.springer.com/article/10.1007/BF02551274).
  
  [This paper](http://www.sciencedirect.com/science/article/pii/089360809190009T) goes on to demonstrate that this is true for a wide range of activation functions (not necessarily nonlinear). 3 layer MLPs are also capable of representing any boolean function (although they may require an exponential number of neurons).
  
  See also [this interesting answer](https://cstheory.stackexchange.com/questions/7894/universal-function-approximation) on CS SE about other Universal approximators.
  
  
  ---
  
  