5
$\begingroup$

Is there literature on how big a net needs to be to learn an arbitrary classification problem where the input is a n-bit integer and the output is one of k categories? I'm interested in both a theoretical bound and the size needed in practice with current training and initialization techniques.

To be specific, the neural net is allowed to see all possible inputs and their respective outputs, so I will not hide anything from the training set, as the function is not assumed to have any structure whatsoever.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Any bounds would not be strictly based on the number of categories, but the complexity of the decision boundaries. If the boundaries are simple hyperplanes in the input space, then you would need no hidden layers and only one output neuron per category. Most interesting problems are not so simple though. $\endgroup$
    – Neil Slater
    Sep 2, 2016 at 7:03
  • $\begingroup$ What does n-int integer input mean? Is it discrete and capped? $\endgroup$
    – Jan van der Vegt
    Sep 2, 2016 at 7:42
  • $\begingroup$ Discrete yes, I'm asking for a maximum complexity case here. $\endgroup$
    – davik
    Sep 2, 2016 at 8:01
  • 1
    $\begingroup$ @davik: "Maximum" complexity would essentially be learning a random class assgnment for each discrete input. Which would probably require a huge network, and be about as useful a concept as the simple hyperplanes, because the concept of generalisation would not apply, and you may as well just store a lookup table of input to output. Really what you are asking for does not exist. The best size of network depends critically on the nature of your problem, and the advice is usually to try stuff and see what works. $\endgroup$
    – Neil Slater
    Sep 2, 2016 at 13:18
  • $\begingroup$ I am basically asking how big it needs to be to learn to be a lookup table, this is mainly out of theoretical interest to me $\endgroup$
    – davik
    Sep 2, 2016 at 16:29

2 Answers 2

Reset to default
9
$\begingroup$

The size of the Neural Network is usually treated as a hyper-parameter. You need to estimate it from a separate cross-validation set.

For Neural nets there are no theoretical proven bounds (there are some papers here and there, but they are not applicable in practice).

You need to use the good old "cross-validation" method to search for the best fit value of the size of NN.

P.S. : There is a paper from Yoshua Bengio with all trick and traits for training such machines.

https://arxiv.org/abs/1206.5533

Improve this answer
$\endgroup$
3
$\begingroup$

Let's look at some specific tasks.

Input is the bytecode of a program, as integers.

Let's use a program that computes prime numbers. I'm pretty sure you can write such a program in a reasonably small number of bytes. Let's add another integer, the number of primes we want to find. The output would be whether the second highest bit of the prime is 0 or 1 (i.e. if the prime begins with 0...010 or 0...011) Just two classes.

Alternatively, let the input be a program, and the output whether the program halts, or not (cf. "halting problem").

I'm pretty sure, not even the largest neural network can predict the output reliably of these two examples even if you bound the input length. So there is no guarantee of being able to learn anything with just enough nodes. what you can probably guarantee id the ability to overfit. Given N training examples (that have consistent labels), you can build a network with x nodes that perfectly memoizes the training data (but that is unable to generalize, so it is overfitted to the training data).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yes, I agree, what I'm asking is precisely how many it takes to memorize $\endgroup$
    – davik
    Sep 3, 2016 at 20:56
  • 1
    $\begingroup$ But you don't want it to memorize usually. Plus, there is an infinite number of integers. So if by "all possible inputs" you mean every integer, the answer will be infinite. $\endgroup$
    – Has QUIT--Anony-Mousse
    Sep 3, 2016 at 21:04
  • $\begingroup$ I agree that this is against the usual use case for neural networks. Also I'm limiting the number of bits of input, I'm wondering if there is literature on this somewhere. $\endgroup$
    – davik
    Sep 3, 2016 at 22:34
  • 1
    $\begingroup$ With "n-int integer", do you mean "n-bit integer" then? Also, I would avoid the use of "learning" here, but prefer the term "encode". You want to encode all 2^n binary answers? Assuming n binary inputs, 2^n nodes should be able to store all desired outputs. $\endgroup$
    – Has QUIT--Anony-Mousse
    Sep 4, 2016 at 6:47
  • 1
    $\begingroup$ I'm pretty dure the 2^n can be improved if you only have few output classes, but it supposedly remains O(n^2) if the output values were assigned randomly. $\endgroup$
    – Has QUIT--Anony-Mousse
    Sep 4, 2016 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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