Let's assume some arbitrary labeled training data. Maybe generated just completely random. Does a neural network exist which converges on the training data?

With convergence, I mean that the network describes the training data to high accuracy. I don't want to define high accuracy because this might limit the answers I get.

Further, the question is related to: For every training data does a neural network exist which finds some kind of pattern to achieve high accuracy?

Or to turn it around, given some accuracy acc in the interval [0,1] and some arbitrary training data, can I find a neural network which will at least reach the given accuracy?
The last one is theoretical and practical question. What would it take to reach the given accuracy. Is it possible in a few minutes for an experienced AI expert or are we talking about centuries of training which is practically unrealistic (currently without quantum computing).

Edit: As mentioned in the comments, for arbitrary pairs of input/ouput values it is simple to construct a counter example such that there is no neural network to solve the problem.
What if the input must be unique, such that the input values can only occur once with arbitrary labels?

Edit 2: The 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 Rn, ... (see https://en.wikipedia.org/wiki/Universal_approximation_theorem).

Further, Michael Nielsen states 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 (see http://neuralnetworksanddeeplearning.com/chap4.html).

So for continous functions this seems plausible. Interestingly Nielsen mentioned any function, which he also explains as problematic and he basically gets to continous functions which might approximate non continous functions well enough.

My problem here is, that the theorem assumes that there is some kind of (continous) function. And my question is basically, does a neural network - or more precise the learning algorithm - always find some pattern given some random input? So, can a neural network theoretically be used to show that a correlation between input/output exists or do examples exist where the network will never converge.

To ask it differently: Will I always be able to find a network which finds the most absurd correlations I want it to find?

  • 2
    $\begingroup$ Simple counterexample showing that there are training data for which this isn't possible: consider a network with one input and one output. Train it with the data (0,0) and (0,1). Now, which output should it learn? $\endgroup$ – Hans-Martin Mosner Nov 7 '19 at 12:18
  • $\begingroup$ @Hans-MartinMosner Can you please elaborate your comment a bit? With (0,1) you mean, input value 0 and output value 1? So the same input has two different labels? If thats what you meant, I think I understand your argument, but its not what I meant. The idea was that each pair of training input and label is unique, so e.g. an image of a cat is only a cat and not a cat and a dog $\endgroup$ – John Doe Nov 7 '19 at 13:21
  • 1
    $\begingroup$ Well I see that my question allows your answer. I'll edit my question to add a more plausible assumption $\endgroup$ – John Doe Nov 7 '19 at 13:22
  • $\begingroup$ The real problem with the question is that even when you tune it to avoid the loophole I've shown it is too open-ended. There are many classes of neural networks, many training algorithms, possibly many more that haven't been invented yet, so it is likely impossible to find a definitive answer. $\endgroup$ – Hans-Martin Mosner Nov 7 '19 at 13:41
  • $\begingroup$ @Hans-MartinMosner I've edited the question. Many thanks for your scepticism $\endgroup$ – John Doe Nov 7 '19 at 14:20

The branch of AI research that answers questions like this is called 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.

|improve this answer|||||

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.