I want to know whether a given neural network (with a finite number of nodes) is able to store all injective maps f: D -> C, where D has cardinality k and C has cardinality N (so the number of maps is N! over (N-k)! ). For example is a network with 1000 nodes able to store 60 injective maps from {1,2,3} to {1,2,3,4,5}?

(By storing information I mean something like: when classifying information the network can access and use the information)

In particular I was curious if the above question can be translated to a question about the VC-dimension of a neural network. Can a question about storing injective maps in a neural network be translated to a question about the VC-dimension of a neural network?

EDIT: I’m interested in something like the following result

There are 60 functions, note that we can represent this with 6 bits The codomain consists of 5 elements, which can be encoded by 3 bits (since 5 < 2^3) We need to map 3 elements of the domain to an element of the co-domain, so we need 3 times 3 bits for each function So to encode 60 functions we need 60 * 3 * 3 bits

In general we need (N! / (N-k)! ) * k * log_2(N) bits Note that (N-k+1)^k < N! / (N-k)! < N^k and even (N-k)^k < (N! / (N-k)! ) * k * log_2(N) < N^k

One weight in a neural network is 32 bits If we have X weights, then we have X*32 bits

So if X*32 is smaller than log_2(N-k) * k, then it’s not possible to express all the functions in the network [I’m actually more interested in negative results like the one I gave, sorry if that’s confusing. Positive results are welcome as well.]

  • $\begingroup$ I'm not sure what your question is. It sounds like you've already got an answer, so I'm not sure what you need us for. $\endgroup$
    – D.W.
    Oct 3 '20 at 21:36

You're probably not going to get a theoretical answer, because analyzing exactly what set of functions can be computed by a particular neural network is messy. Or, at least, you probably won't get a tight analysis. There are theorems showing that neural networks are universal approximators, meaning that given sufficient capacity it is possible to express every function, but this doesn't tell you the minimize size needed to express every function; it just tells you that there exists a size that is large enough.

However, if you're willing to accept empirical evidence rather than theorems and proofs, research has demonstrated empirically that if you choose a deep neural network architecture with sufficient capacity and you train for long enough, neural nets can memorize the training set and achieve 100% accuracy on the training set, at least for a randomly chosen function $f$ [1]. This may not tell you exactly what size neural network you need to ensure that it can express all such functions, and it's not a proof or a guarantee.

The VC dimension is beautiful theory but it's not clear it has a great deal of relevance to modern use of neural networks in practice.

[1] Understanding deep learning requires rethinking generalization. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals. arXiv:1611.03530


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.