Answers.Body: <p>The branch of AI research that answers questions like this is called <a href="https://en.wikipedia.org/wiki/Computational_learning_theory" rel="nofollow noreferrer">computational learning theory</a>.</p>
  
  <p>For the specific question you have asked, the universal approximation theorem does indeed prove that any function can be modeled by a sufficiently wide neural network. The definition of a function includes the requirement that each input be mapped to exactly one output, so contradictory labels in training data are excluded explicitly.</p>
  
  <p>Here is a rough sketch that can provide an intuition behind why this is true. This is not a proper proof, but it gives you an idea of the power of "finite number of neurons" in a hidden layer:</p>
  
  <ol>
  <li>A single neuron can essentially learn to draw a straight line across the space of input features. It outputs a value arbitrarily close to 1 for things on one side of the line, and arbitrarily close to 0 for things on the other side of the line.</li>
  <li>For any given datapoint, it is possible to enclose the hyper-volume containing that datapoint, and <em>no others</em> by drawing a series of lines in the input space, and defining one side of each line as "inside" the hyper-volume, and the other side as "outside". In 2-d space, this corresponds to drawing the 4 sides of a square around a point.</li>
  <li>An output neuron learns to draw lines across the outputs of the hidden layer neurons. It can therefore decide to output 1 only when, say, 4 other neurons are all simultaneously active. </li>
  </ol>
  
  <p>It should seem natural then that a sufficiently wide neural network can <em>memorize</em> all of an input pattern. Since memorization is sufficient for "learning" to fit a pattern this should give you an intuition for the ability of neural networks to fit things.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-07T14:28:19.547Z
Answers.LastActivityDate: 2019-11-07T22:54:36.267Z
Answers.LastEditDate: 2019-11-07T22:54:36.267Z
Answers.UserDisplayName: John Doucette
Body: <p>The <a href="https://en.wikipedia.org/wiki/Universal_approximation_theorem" rel="nofollow noreferrer">universal approximation theorem</a> states, that a feed-forward network with a single hidden layer containing a finite number of neurons can approximate continuous functions on compact subsets of <span class="math-container">$R^n$</span>.</p>
  <p><a href="http://neuralnetworksanddeeplearning.com/chap4.html" rel="nofollow noreferrer">Michael Nielsen states</a></p>
  <blockquote>
  <p>No matter what the function, there is guaranteed to be a neural network so that for every possible input, <span class="math-container">$x$</span>, the value <span class="math-container">$f(x)$</span> (or some close approximation) is output from the network.</p>
  </blockquote>
  <p>So, for continuous functions, this seems plausible. Interestingly, in the same article, Nielsen mentioned &quot;any function&quot;.</p>
  <p>Later, he writes</p>
  <blockquote>
  <p>However, even if the function we'd really like to compute is discontinuous, it's often the case that a continuous approximation is good enough.</p>
  </blockquote>
  <p>The last statement leaves open a gap, to ask how well an approximation practically can be.</p>
  <p>Let's ignore contradictory input/output training pairs like <span class="math-container">$f(0)=0$</span> and <span class="math-container">$f(0)=1$</span>, which actually don't event represent a function anyway.</p>
  <p>Furthermore, assume that the training data is generated randomly, which would practically result in a discontinuous function.</p>
  <p>How does a neural network learn such data? Will a learning algorithm always be able to find a neural network that approximates the function represented by the input-output pairs?</p>
  
Tags: <neural-networks><computational-learning-theory><universal-approximation-theorems>
Title: Does a neural network exist that can learn every possible training data?
UserDisplayName: John Doe
ThreadText: # Does a neural network exist that can learn every possible training data?
  
  (Asked by: username_0 on 2019-11-07)
  
  The [universal approximation theorem](https://en.wikipedia.org/wiki/Universal_approximation_theorem) states, that a feed-forward network with a single hidden layer containing a finite number of neurons can approximate continuous functions on compact subsets of $R^n$.
  
  [Michael Nielsen states](http://neuralnetworksanddeeplearning.com/chap4.html)
  
  > No matter what the function, there is guaranteed to be a neural network so that for every possible input, $x$, the value $f(x)$ (or some close approximation) is output from the network.
  
  So, for continuous functions, this seems plausible. Interestingly, in the same article, Nielsen mentioned "any function".
  
  Later, he writes
  
  > However, even if the function we'd really like to compute is discontinuous, it's often the case that a continuous approximation is good enough.
  
  The last statement leaves open a gap, to ask how well an approximation practically can be.
  
  Let's ignore contradictory input/output training pairs like $f(0)=0$ and $f(0)=1$, which actually don't event represent a function anyway.
  
  Furthermore, assume that the training data is generated randomly, which would practically result in a discontinuous function.
  
  How does a neural network learn such data? Will a learning algorithm always be able to find a neural network that approximates the function represented by the input-output pairs?
  
  **Tags:** neural-networks, computational-learning-theory, universal-approximation-theorems
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-11-07. Score: 1 | Accepted answer
  
  The branch of AI research that answers questions like this is called [computational learning theory](https://en.wikipedia.org/wiki/Computational_learning_theory).
  
  For the specific question you have asked, the universal approximation theorem does indeed prove that any function can be modeled by a sufficiently wide neural network. The definition of a function includes the requirement that each input be mapped to exactly one output, so contradictory labels in training data are excluded explicitly.
  
  Here is a rough sketch that can provide an intuition behind why this is true. This is not a proper proof, but it gives you an idea of the power of "finite number of neurons" in a hidden layer:
  
  1. A single neuron can essentially learn to draw a straight line across the space of input features. It outputs a value arbitrarily close to 1 for things on one side of the line, and arbitrarily close to 0 for things on the other side of the line.
  2. For any given datapoint, it is possible to enclose the hyper-volume containing that datapoint, and *no others* by drawing a series of lines in the input space, and defining one side of each line as "inside" the hyper-volume, and the other side as "outside". In 2-d space, this corresponds to drawing the 4 sides of a square around a point.
  3. An output neuron learns to draw lines across the outputs of the hidden layer neurons. It can therefore decide to output 1 only when, say, 4 other neurons are all simultaneously active.
  
  It should seem natural then that a sufficiently wide neural network can *memorize* all of an input pattern. Since memorization is sufficient for "learning" to fit a pattern this should give you an intuition for the ability of neural networks to fit things.
  
  
  ---
  
  